Space O(N), recursive solution.


  • 0
    C
     public class Solution {
        public boolean wordPatternMatch(String pattern, String str) {
            HashMap map = new HashMap();
            return dfs(pattern, 0, str, 0, map);
        }
        private boolean dfs(String pattern, int i, String str, int j, HashMap map){
            if(i == pattern.length() && j == str.length()){
                return true;
            }
            if(i == pattern.length() || j == str.length()){
                return false;
            }
            char c = pattern.charAt(i);
            for(int k = j; k < str.length(); k++){
                if(map.get(c) == map.get(str.substring(j, k+1))){
                    Integer val = (Integer)map.get(c);
                    if(val == null){
                        map.put(pattern.charAt(i), i);
                        map.put(str.substring(j, k+1), i);
                    }
                    if(dfs(pattern, i+1, str, k+1, map)){
                        return true;
                    }
                    if(val == null){
                        map.remove(pattern.charAt(i));
                        map.remove(str.substring(j, k+1));
                    }
                }
            }
            return false;
        }
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.