> For the complete documentation index, see [llms.txt](https://kerasnoone.gitbook.io/garnet/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://kerasnoone.gitbook.io/garnet/suan-fa/zi-fu-chuan/16.18-mo-shi-pi-pei.md).

# \[面试题 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
```