291 Word Pattern II

291. Word Pattern II​
1. Question
Given apatternand a stringstr, find ifstrfollows the same pattern.
Here follow means a full match, such that there is a bijection between a letter inpatternand a non-empty substring instr.
Examples:
1.pattern ="abab", str ="redblueredblue"should return true.
2.pattern ="aaaa", str ="asdasdasdasd"should return true.
3.pattern ="aabb", str ="xyzabcxzyabc"should return false.
Notes:
You may assume bothpatternandstrcontains only lowercase letters.
2. Implementation
(1) Backtracking
1
class Solution {
2
    public boolean wordPatternMatch(String pattern, String str) {
3
        Map<Character, String> map = new HashMap<>();
4
        Set<String> set = new HashSet<>();
5
        return isMatched(pattern, 0, str, 0, set, map);
6
    }
7
​
8
    public boolean isMatched(String pattern, int patternIndex, String str, int strIndex, Set<String> set, Map<Character, String> map) {
9
        if (patternIndex == pattern.length() && strIndex == str.length()) {
10
            return true;
11
        }
12
​
13
        // 没有足够的部分完成匹配
14
        if (patternIndex == pattern.length() || strIndex == str.length() 
15
            || str.length() - strIndex < pattern.length() - patternIndex) {
16
            return false;
17
        }
18
​
19
        char c = pattern.charAt(patternIndex);
20
​
21
        // 如果当前字符c已经有匹配的string
22
        if (map.containsKey(c)) {
23
            String matchedStr = map.get(c);
24
​
25
            // 如果string剩余的部分并非以已匹配的string开头的话，则pattern不match
26
            if (!str.startsWith(matchedStr, strIndex)) {
27
                return false;
28
            }
29
            return isMatched(pattern, patternIndex + 1, str, strIndex + matchedStr.length(), set, map);
30
        }
31
        // 如果当前字符c目前没有匹配的string, 尝试match各种可能的string
32
        else {
33
            for (int i = strIndex; i < str.length(); i++) {
34
                String candidate = str.substring(strIndex, i + 1);
35
​
36
                // 利用HashSet防止不同的字符对应一样的string
37
                if (set.contains(candidate)) {
38
                    continue;
39
                }
40
​
41
                set.add(candidate);
42
                map.put(c, candidate);
43
​
44
                if (isMatched(pattern, patternIndex + 1, str, i + 1, set, map)) {
45
                    return true;
46
                }
47
​
48
                map.remove(c);
49
                set.remove(candidate);
50
            }
51
            return false;
52
        }
53
    }
54
}
Copied!
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

267 Palindrome Permutation II

320 Generalized Abbreviation

Last modified 2yr ago

Copy link

Contents

291. Word Pattern II

1. Question

2. Implementation

3. Time & Space Complexity

291. Word Pattern II​

1. Question

2. Implementation

3. Time & Space Complexity

291. Word Pattern II