[面试题 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模式各自对应的子串所有可能的长度, 然后判别是否整体是否匹配.

参考:

• 模式匹配

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