# \[面试题 16.18]\[中等] 模式匹配

## 题目描述

你有两个字符串，即pattern和value。 pattern字符串由字母"a"和"b"组成，用于描述字符串中的模式。例如，字符串"catcatgocatgo"匹配模式"aabab"（其中"cat"是"a"，"go"是"b"），该字符串也匹配像"a"、"ab"和"b"这样的模式。但需注意"a"和"b"不能同时表示相同的字符串。编写一个方法判断value字符串是否匹配pattern字符串。

示例 1：

```
输入： pattern = "abba", value = "dogcatcatdog"
输出： true
```

示例 2：

```
输入： pattern = "abba", value = "dogcatcatfish"
输出： false
```

示例 3：

```
输入： pattern = "aaaa", value = "dogcatcatdog"
输出： false
```

示例 4：

```
输入： pattern = "abba", value = "dogdogdogdog"
输出： true
解释： "a"="dogdog",b=""，反之也符合规则
```

提示：

* 0 <= len(pattern) <= 1000
* 0 <= len(value) <= 1000
* 你可以假设pattern只包含字母"a"和"b"，value仅包含小写字母。

## 解题思路

简单来说就是枚举`a`模式和`b`模式各自对应的子串所有可能的长度, 然后判别是否整体是否匹配.

参考:

* [模式匹配](https://leetcode-cn.com/problems/pattern-matching-lcci/solution/mo-shi-pi-pei-by-leetcode-solution/)

```python
class Solution:
    def patternMatching(self, pattern: str, value: str) -> bool:
        n, m = len(value), len(pattern)
        if m == 0:
            return True if n == 0 else False

        first, second = 'a', 'b'
        first_num = sum([t == first for t in pattern])
        second_num = m - first_num
        if second_num > first_num:
            first, second = second, first
            first_num, second_num = second_num, first_num

        if n == 0:
            return True if second_num == 0 else False

        available = []
        len_first, len_second = 0, 0
        while len_first <= n:
            if second_num == 0:
                if len_first > 0:
                    available.append((len_first, 0))
            else:
                len_second = (n - len_first * first_num) / second_num
                if len_second < 1:
                    break
                if (n - len_first * first_num) % second_num == 0:
                    available.append((len_first, int(len_second)))
            len_first += 1

        if not available:
            return False

        for flen, slen in available:
            f, s = None, None
            cur, bfalse = 0, 0
            for i, t1 in enumerate(pattern):
                if t1 == first:
                    tmp = value[cur: cur + flen]
                    if f is None:
                        f = tmp
                    else:
                        if tmp != f:
                            bfalse = 1
                            break
                    cur += flen
                else:
                    tmp = value[cur: cur + slen]
                    if s is None:
                        s = tmp
                    else:
                        if tmp != s:
                            bfalse = 1
                            break
                    cur += slen
            if cur == n and i == m - 1 and not bfalse:
                return True
        return False
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://kerasnoone.gitbook.io/garnet/suan-fa/zi-fu-chuan/16.18-mo-shi-pi-pei.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.