Leetcode 291 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: Use back tracking.

 public class Solution {  
   public boolean wordPatternMatch(String pattern, String str) {  
     Map<Character,String> map1=new HashMap<>();  
     Map<String,Character> map2=new HashMap<>();  
     if (str.length()<pattern.length()) return false;  
     return dfs(map1,map2,pattern,str,0,0);  
   }  
   private boolean dfs(Map<Character,String> map1, Map<String,Character> map2, String pattern, String str, int i, int j) {  
     if (i==pattern.length() && j==str.length()) return true;  
     if (i==pattern.length() || j==str.length()) return false;  
     char c=pattern.charAt(i);  
     if (map1.containsKey(c)) {  
       String s=map1.get(c);  
       int len=s.length();  
       if (j+len>str.length()) return false;  
       if (!s.equals(str.substring(j,j+len))) return false;  
       return dfs(map1,map2,pattern,str,i+1,j+len);  
     }  
     else {  
       for (int k=j+1; k<=str.length(); k++) {  
         String s=str.substring(j,k);  
         if (map2.containsKey(s)) continue;  
         map1.put(c,s);  
         map2.put(s,c);  
         if (dfs(map1,map2,pattern,str,i+1,k)) return true;  
         map1.remove(c);  
         map2.remove(s);  
       }  
       return false;  
     }  
   }  
 }