Word Pattern II

Given a pattern and a string str, find if str follows the same pattern.
Here follow means a full match, such that there is a bijection between a letter in pattern and a non-empty substring in str.
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 both pattern and str contains only lowercase letters.
Solution:
1. public class Solution {
2. public boolean wordPatternMatch(String pattern, String str) {
3. Map map = new HashMap<>();
4. Set set = new HashSet<>();
5. 6. return isMatch(str, 0, pattern, 0, map, set);
7. }
8. 9. boolean isMatch(String str, int i, String pat, int j, Map map, Set set) {
10. // base case
11. if (i == str.length() && j == pat.length()) return true;
12. if (i == str.length() || j == pat.length()) return false;
13. 14. // get current pattern character
15. char c = pat.charAt(j);
16. 17. // if the pattern character exists
18. if (map.containsKey(c)) {
19. String s = map.get(c);
20. 21. // then check if we can use it to match str[i...i+s.length()]
22. if (!str.startsWith(s, i)) {
23. return false;
24. }
25. 26. // if it can match, great, continue to match the rest
27. return isMatch(str, i + s.length(), pat, j + 1, map, set);
28. }
29. 30. // pattern character does not exist in the map
31. for (int k = i; k < str.length(); k++) {
32. String p = str.substring(i, k + 1);
33. 34. if (set.contains(p)) {
35. break;
36. }
37. 38. // create or update it
39. map.put(c, p);
40. set.add(p);
41. 42. // continue to match the rest
43. if (isMatch(str, k + 1, pat, j + 1, map, set)) {
44. return true;
45. }
46. }
47. 48. // we've tried our best but still no luck
49. // backtracking
50. set.remove(map.get(c));
51. map.remove(c);
52. 53. return false;
54. }
55. }