难度: Medium
Submission
运行时间: 27 ms
内存: 0.0 MB
class Solution:
def wordPatternMatch(self, pattern: str, s: str) -> bool:
# Backtracking
# Inputs:
# dict1: char to word
# dict2: word to char
# remaining pattern and s
n1, n2 = len(pattern), len(s)
if n1 == 0 and n2 == 0:
return True
if n1 == 1 and n2 > 0:
return True
return self.backtracking(dict(), dict(), pattern, s)
def backtracking(self, dict1, dict2, pattern, s):
print(dict1, dict2, pattern, s)
n1, n2 = len(pattern), len(s)
if n1 == 0 and n2 == 0:
return True
elif n1 == 0 and n2 > 0:
return False
elif n1 > 0 and n2 == 0:
return False
else:
c = pattern[0]
if c in dict1:
word1 = dict1[c]
if (word1 not in dict2) or (dict2[word1] != c):
return False
l = len(word1)
word2 = s[:l]
if word2 != word1:
return False
else:
return self.backtracking(dict1, dict2, pattern[1:], s[l:])
else:
for l in range(1, n2-n1+2):
word = s[:l]
if word in dict2:
continue
dict1New, dict2New = dict1.copy(), dict2.copy()
dict1New[c] = word
dict2New[word] = c
flag = self.backtracking(dict1New, dict2New, pattern[1:], s[l:])
if flag:
return True
return False
Explain
这是一道使用回溯法解决的问题。主要思路是将模式字符串pattern和单词字符串s同时进行匹配和拆分。使用两个字典dict1和dict2分别存储模式字符到单词、单词到模式字符的映射关系。在回溯过程中，如果当前模式字符已经有映射的单词，则检查映射是否一致；如果当前模式字符还没有映射单词，则枚举当前单词字符串的所有前缀作为可能的映射，递归处理剩余的模式字符串和单词字符串。如果匹配成功则返回True，否则继续尝试其他的映射方案，直到所有可能的映射组合都尝试完毕。
时间复杂度: O(m^n)
空间复杂度: O(n)
class Solution:
def wordPatternMatch(self, pattern: str, s: str) -> bool:
# Backtracking
# Inputs:
# dict1: char to word
# dict2: word to char
# remaining pattern and s
n1, n2 = len(pattern), len(s)
if n1 == 0 and n2 == 0:
return True
if n1 == 1 and n2 > 0:
return True
return self.backtracking(dict(), dict(), pattern, s)
def backtracking(self, dict1, dict2, pattern, s):
print(dict1, dict2, pattern, s)
n1, n2 = len(pattern), len(s)
if n1 == 0 and n2 == 0:
# Base case: both pattern and s are empty, match successfully
return True
elif n1 == 0 and n2 > 0:
# Pattern is empty but s is not, match fails
return False
elif n1 > 0 and n2 == 0:
# Pattern is not empty but s is empty, match fails
return False
else:
c = pattern[0]
if c in dict1:
# Current pattern char is already mapped to a word
word1 = dict1[c]
if (word1 not in dict2) or (dict2[word1] != c):
# Mapping is inconsistent, match fails
return False
l = len(word1)
word2 = s[:l]
if word2 != word1:
# Current substring doesn't match the mapped word, match fails
return False
else:
# Current substring matches the mapped word, recursively match the remaining parts
return self.backtracking(dict1, dict2, pattern[1:], s[l:])
else:
# Current pattern char is not mapped, try all possible mappings
for l in range(1, n2-n1+2):
word = s[:l]
if word in dict2:
# Current substring is already mapped to another pattern char, skip
continue
dict1New, dict2New = dict1.copy(), dict2.copy()
dict1New[c] = word
dict2New[word] = c
flag = self.backtracking(dict1New, dict2New, pattern[1:], s[l:])
if flag:
# Found a valid mapping, return True
return True
# Tried all possible mappings but none works, return False
return False
Explore
在递归过程中，每次尝试建立新的映射时，都会创建dict1和dict2的副本。这样，每个递归调用都有自己的字典副本，不会影响到其他递归分支的字典状态。当递归函数尝试并回退某一路径时，之前的字典状态因为使用副本，所以仍保持未更改的状态，从而确保每次递归中映射的一致性。
算法确实保证了模式字符到单词的双向唯一性映射。首先，通过检查当前单词是否已存在于dict2中，确保不会将一个单词映射到多个模式字符。其次，每次建立新映射时，同时更新dict1和dict2，确保从模式字符到单词和从单词到模式字符的映射都是一致的。如果任一映射已存在冲突，则不会尝试该映射，从而维持了双向唯一性。
在递归函数中提前返回False可以有效剪枝，即在确定当前路径不可能导致成功匹配的情况下，及时停止进一步的无效递归调用，从而减少计算量和提高算法效率。这种设计在处理复杂的回溯问题时尤为重要，因为它可以避免在已知失败的路径上浪费计算资源。
循环的范围`range(1, n2-n1+2)`是基于剩余模式字符和剩余单词长度的关系来确定的。这个范围确保了，即使每个剩余的模式字符至少映射一个单词字符，仍有足够的单词字符可供映射。例如，若剩余模式长度为1，那么应该考虑将所有剩余的单词字符串作为一个可能的映射，而如果剩余模式长度等于剩余单词长度，每个模式字符只能映射一个单词字符，因此这个范围可以动态调整映射尝试的长度，以适应不同的模式和单词长度情况。