此题解采用模拟和试探的方法来决定两种模式 'a' 和 'b' 可能对应的字符串长度,通过穷举所有可能的长度组合。首先计算 pattern 中 'a' 和 'b' 的出现次数。如果 value 为空字符串,只有在 pattern 也不含 'a' 或 'b' 时才返回真。特殊情况处理,若 'a' 或 'b' 出现次数为1,那么总可以将 value 分配给那个模式字符。接下来,尝试每一个可能的 'a' 的长度 (len_a),计算相应的 'b' 的长度。通过字典 d 存储 'a' 和 'b' 对应的字符串和长度。遍历 pattern,检查对应段的字符串是否匹配,如果遇到不匹配的情况则结束当前循环。如果整个 pattern 遍历完成也没有中断,说明找到了一种匹配方式。
时间复杂度: O(n^2)
空间复杂度: O(1)
class Solution:
def patternMatching(self, pattern: str, value: str) -> bool:
cnta = pattern.count('a') # 统计 'a' 的数量
cntb = len(pattern) - cnta # 统计 'b' 的数量
if not value: # 如果 value 为空
return not (cnta and cntb) # 只有 'a' 或 'b' 其中一个为0时返回 True
if cnta == 1 or cntb == 1: # 如果 'a' 或 'b' 的数量为1
return True # 直接返回 True
n = len(value) # value 的长度
if not (cnta and cntb): # 如果 'a' 或 'b' 其中一个为0
c = cnta or cntb # 获取非零的数量
if n % c: # 如果不能整除则返回 False
return False
s = value[:n // c] # 取得对应的子串
return bool(re.match(f'{s}{{{c}}}', value)) # 检查模式是否匹配
for len_a in range(n): # 尝试每一个可能的 'a' 的长度
total_a = len_a * cnta # 计算 'a' 对应的总长度
rest = n - total_a # 剩余长度
len_b, t = divmod(rest, cntb) # 计算 'b' 的长度和剩余部分
if t: # 如果剩余部分不为0,继续下一轮
continue
d = {'a':[None, len_a], 'b':[None, len_b]} # 存储 'a' 和 'b' 的字符串和长度
i = 0
for c in pattern: # 遍历 pattern
if d[c][0] is None: # 如果还没有确定对应的字符串
d[c][0] = value[i:i + d[c][1]] # 确定对应的字符串
if d['a'][0] == d['b'][0]: # 如果 'a' 和 'b' 对应相同的字符串
break
elif value[i:i + d[c][1]] != d[c][0]: # 如果当前段不匹配
break
i += d[c][1] # 更新下一段的起始索引
else: # 如果遍历完 pattern 没有中断
return True # 返回 True
return False # 如果尝试所有可能都失败,返回 False