面试题 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=""，反之也符合规则

提示：

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

Python 解答：
1.二元一次方程

class Solution:
    def patternMatching(self, pattern: str, value: str) -> bool:
        lens = len(value)
        if pattern[0] == 'b':
            string = ""
            for i in range(len(pattern)):
                if pattern[i] == 'b':
                    string += 'a'
                else:
                    string += 'b'
            pattern = string

        num_a = pattern.count('a')
        num_b = pattern.count('b')

        if not lens:
            # if (num_a == 1 and not num_b) or (num_b == 1 and not num_a):
            if (num_a == 1 and not num_b):
                return True
            else:
                return False
        # if not num_a:
        #     if lens % num_b != 0:
        #         return False
        #     num2 = lens//num_b
        #     for j in range(len(pattern)):
        #         if value[0:num2] != value[j*num2:(j+1)*num2]:
        #             return False
        #     else:
        #         return True
        if not num_b:
            if lens % num_a != 0:
                return False
            num1 = lens//num_a
            for j in range(len(pattern)):
                if value[0:num1] != value[j*num1:(j+1)*num1]:
                    return False
            else:
                return True            

        num1 = lens//num_a
        num2 = lens//num_b
        for i in range(num2+1):
            k = None
            if (lens-i*num_b) % num_a == 0:
                k = (lens-i*num_b)//num_a
            else: continue
            word_a = value[0:k]
            word_b = None
            for m in range(1, len(pattern)):
                if pattern[m] == 'b':
                    word_b = value[m*k:m*k+i]
                    break
            index = 0
            for j in range(len(pattern)):
                if pattern[j] == 'a':
                    if word_a != value[index:index+k]:
                        break
                    else:
                        index += k
                else: 
                    if word_b != value[index:index+i]:
                        break
                    else:
                        index += i
            else:
                return True
        return False