- 1 public class Solution {
- 2 public boolean wordPatternMatch(String pattern, String str) {
- 3 HashMap hm = new HashMap();
- 4 HashSet hs = new HashSet();
- 5
- return isMatch(pattern, 0, str, 0, hm, hs);
- 6
- }
- 7 8 private boolean isMatch(String pattern, int i, String str, int j, HashMap hm, HashSet hs) {
- 9 //stop condition
- 10
- if (i == pattern.length() && j == str.length()) {
- 11
- return true;
- 12
- }
- 13
- if (i == pattern.length() || j == str.length()) {
- 14
- return false;
- 15
- }
- 16 17 char c = pattern.charAt(i);
- 18 19 //If current pattern character already exists in map
- 20
- if (hm.containsKey(c)) {
- 21 String cString = hm.get(c);
- 22 23 //If corresponding string does not match str.substring(j, j+matchedString.length()).
- 24
- if (!str.startsWith(cString, j)) {
- 25
- return false;
- 26
- }
- 27
- return isMatch(pattern, i + 1, str, j + cString.length(), hm, hs);
- 28
- } else {
- 29 //current pattern character doesn't exist in the map
- 30
- for (int k = j; k) {
- 31 String s = str.substring(j, k + 1);
- 32 33 //different strings can't be matched to same char
- 34
- if (hs.contains(s)) {
- 35
- continue;
- 36
- }
- 37 38 hm.put(c, s);
- 39 hs.add(s);
- 40 41 //if all reset string could be matched
- 42
- if (isMatch(pattern, i + 1, str, k + 1, hm, hs)) {
- 43
- return true;
- 44
- }
- 45 46 hm.remove(c);
- 47 hs.remove(s);
- 48
- }
- 49 50 //Have tried all different lengths
- 51
- return false;
- 52
- }
- 53
- }
- 54
- }
来源: