05 August 2008
给定一个模式和一个字符串 s，如果 s 匹配该模式，则返回 true。
如果单个字符到字符串存在某种双射映射，那么如果模式中的每个字符都被它映射到的字符串替换，则字符串 s 匹配模式，则结果字符串是 s。双射映射意味着没有两个字符映射到同一个字符串，也没有字符映射到两个不同的字符串。
背包问题
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
class Solution {
/*
https://leetcode.com/problems/word-pattern-ii/discuss/73664/Share-my-Java-backtracking-solution
背包
*/
public boolean wordPatternMatch(String pattern, String str) {
Map<Character, String> map = new HashMap<>();
Set<String> set = new HashSet<>();
return isMatch(str, 0, pattern, 0, map, set);
}
boolean isMatch(String str, int i, String pattern, int j, Map<Character, String> map, Set<String> set) {
// base case
if (i == str.length() && j == pattern.length()) {
return true;
}
if (i == str.length() || j == pattern.length()) {
return false;
}
//get current pattern character
char c = pattern.charAt(j);
// if the pattern character exists
if (map.containsKey(c)) {
String s = map.get(c);
// 检查是否可以用这个pattern来match str[i...i+s.length()]
if (!str.startsWith(s, i)) {
return false;
}
// if it can match, 接着match剩下的
return isMatch(str, i + s.length(), pattern, j + 1, map, set);
}
//pattern character在map中不存在
for (int k = i; k < str.length(); k++) {
String p = str.substring(i, k + 1);
if (set.contains(p)) {
continue;
}
//create of update it
map.put(c, p);
set.add(p);
// contine to match the rest
if (isMatch(str, k + 1, pattern, j + 1, map, set)) {
return true;
}
// 背包
map.remove(c);
set.remove(p);
}
return false;
}
}