LeetCode 291 Word Pattern II

LeetCode

Given a pattern and a string s, return true if s matches the pattern.

A string s matches a pattern if there is some bijective mapping of single characters to strings such that if each character in pattern is replaced by the string it maps to, then the resulting string is s. A bijective mapping means that no two characters map to the same string, and no character maps to two different strings.

Example 1:

Input: pattern = “abab”, s = “redblueredblue”
Output: true
Explanation: One possible mapping is as follows:
‘a’ -> “red”
‘b’ -> “blue”

Example 2:

Input: pattern = “aaaa”, s = “asdasdasdasd”
Output: true
Explanation: One possible mapping is as follows:
‘a’ -> “asd”

Example 3:

Input: pattern = “abab”, s = “asdasdasdasd”
Output: true
Explanation: One possible mapping is as follows:
‘a’ -> “a”
‘b’ -> “sdasd”
Note that ‘a’ and ‘b’ cannot both map to “asd” since the mapping is a bijection.

Example 4:

Input: pattern = “aabb”, s = “xyzabcxzyabc”
Output: false

Constraints:

1 <= pattern.length, s.length <= 20 pattern and s consist of only lower-case English letters.

算法思路：

类似于word break，但由于要存储处理过map和set，DP不能处理，所以只能用DFS

注意事项：

1. 比较映射，用Map比较A->B的映射，如已有a->dog, 另一对映射a->cat通过查找Map知道不合法。B->A的映射可通过将map的所有value存到一个set中知道。如a->dog, b->dog. b不在Map中但b对应的dog在set中，不合法。
   DFS的API为dfs(pattern, word, pattern_to_word, used_set)
2. 若pattern的字母出现过，如aba，不应进入循环，更不应该加入到map和set中，应该用startswith比较word判断是否合法，若是，直接下一轮DFS(Line 11 -15)
3. 1中的两情况的第一种情况以及第二种情况的前半部分(b不在map中)在2中已经处理，所以只要在循环中处理第二种情况后半部分(b对应的dog在set中)即可(Line 22 - 23)

Python代码：

def wordPatternMatch(self, pattern: str, s: str) -> bool:
	if not pattern or not s:
		return False
	return self.dfs(pattern, s, 0, 0, {}, set())

def dfs(self, pattern, s, start_p, start_s, pattern_to_s, s_set):
	if start_p >= len(pattern) and start_s >= len(s):
		return True
	if start_p >= len(pattern) or start_s >= len(s):
		return False
	char = pattern[start_p]
	if char in pattern_to_s:
		word = pattern_to_s[char]
		if not s[start_s:].startswith(word):
			return False
		return self.dfs(pattern, s, start_p + 1, start_s + len(word), pattern_to_s, s_set)
		
	for j in range(start_s, len(s)):
		matched_word = s[start_s:j + 1]
		'''if char in pattern_to_s and pattern_to_s[char] != matched_word:
			continue
		if char not in pattern_to_s and matched_word in s_set:  # remembers
			continue'''
		if matched_word in s_set:
			continue
		pattern_to_s[char] = matched_word
		s_set.add(matched_word)
		if self.dfs(pattern, s, start_p + 1, j + 1, pattern_to_s, s_set):
			return True
		s_set.remove(matched_word)
		pattern_to_s.pop(char)
	return False

算法分析：

时间复杂度为O(解大小)，空间复杂度为O(解大小)。