291 Word Pattern II
291. Word Pattern II
1. Question
Given apattern
and a stringstr
, find ifstr
follows the same pattern.
Here follow means a full match, such that there is a bijection between a letter inpattern
and a non-empty substring instr
.
Examples:
pattern =
"abab"
, str ="redblueredblue"
should return true.pattern =
"aaaa"
, str ="asdasdasdasd"
should return true.pattern =
"aabb"
, str ="xyzabcxzyabc"
should return false.
Notes:
You may assume bothpattern
andstr
contains only lowercase letters.
2. Implementation
(1) Backtracking
class Solution {
public boolean wordPatternMatch(String pattern, String str) {
Map<Character, String> map = new HashMap<>();
Set<String> set = new HashSet<>();
return isMatched(pattern, 0, str, 0, set, map);
}
public boolean isMatched(String pattern, int patternIndex, String str, int strIndex, Set<String> set, Map<Character, String> map) {
if (patternIndex == pattern.length() && strIndex == str.length()) {
return true;
}
// 没有足够的部分完成匹配
if (patternIndex == pattern.length() || strIndex == str.length()
|| str.length() - strIndex < pattern.length() - patternIndex) {
return false;
}
char c = pattern.charAt(patternIndex);
// 如果当前字符c已经有匹配的string
if (map.containsKey(c)) {
String matchedStr = map.get(c);
// 如果string剩余的部分并非以已匹配的string开头的话,则pattern不match
if (!str.startsWith(matchedStr, strIndex)) {
return false;
}
return isMatched(pattern, patternIndex + 1, str, strIndex + matchedStr.length(), set, map);
}
// 如果当前字符c目前没有匹配的string, 尝试match各种可能的string
else {
for (int i = strIndex; i < str.length(); i++) {
String candidate = str.substring(strIndex, i + 1);
// 利用HashSet防止不同的字符对应一样的string
if (set.contains(candidate)) {
continue;
}
set.add(candidate);
map.put(c, candidate);
if (isMatched(pattern, patternIndex + 1, str, i + 1, set, map)) {
return true;
}
map.remove(c);
set.remove(candidate);
}
return false;
}
}
}
3. Time & Space Complexity
Backtracking: 时间复杂度O(n * C(m, n)),n是str的长度, m为pattern的长度,这个问题相当于将str分成m份,而分的方法是C(n, m),每部分都要O(n)时间验证, 空间复杂度O(m + n + n) => O(m + n), 递归的所需空间最多为n, set的空间最多为n, map的空间最多为n
Last updated
Was this helpful?