leetcode [16.18] 模式匹配
Contact me:
Blog -> https://cugtyt.github.io/blog/index
Email -> cugtyt@qq.com
GitHub -> Cugtyt@GitHub
你有两个字符串，即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开始，然后遍历a的所有可能，计算a确定情况下b的起点，然后遍历b的所有可能，如果中间找到了匹配返回，否则没用匹配
class Solution:
def patternMatching(self, pattern: str, value: str) -> bool:
def match(pattern, a, b, value):
return ''.join([a if p == 'a' else b for p in pattern]) == value
if len(value) == 0:
if len(set(pattern)) <= 1: return True
return False
if len(pattern) == 0:
return len(value) == 0
if pattern[0] == 'b': pattern = ''.join(['b' if p == 'a' else 'a' for p in pattern])
a_count = sum(1 for p in pattern if p == 'a')
b_count = len(pattern) - a_count
if pattern[0] == 'b': pattern = ''.join(['b' if p == 'a' else 'a' for p in pattern])
a_count = sum(1 for p in pattern if p == 'a')
b_count = len(pattern) - a_count
for i in range(len(value) + 1):
a = value[:i]
b_start, pattern_i = i, 1
while pattern_i < len(pattern) and b_start < len(value) and value[b_start: b_start + len(a)] == a and pattern[pattern_i] == 'a':
b_start += len(a)
pattern_i += 1
for j in range(b_start, len(value) + 1):
b = value[b_start: j]
if a != b and len(a) * a_count + len(b) * b_count == len(value) and match(pattern, a, b, value):
return True
if len(a) * a_count + len(b) * b_count > len(value):
break
return False