My short AC solution with backtracking


  • 4
    S
    public class Solution {
        Map<Character, String> map = new HashMap<Character, String>(); //keep map of pattern and word
        Set<String> words = new HashSet<String>(); //keep list of word visited
        public boolean wordPatternMatch(String pattern, String str) {
      
            if(pattern.length()==0&&str.length()==0)  //if pattern and str both are empty, pattern matches str
            {
                return true;
            }
            
            //if both pattern and str are not empty, continue matching.
            if(pattern.length()>0&&str.length()>0){
                char c = pattern.charAt(0);
                if(map.get(c)!=null){  //if this char has a str matching
                    if(str.startsWith(map.get(c))){  //continue with sub problem
                        return wordPatternMatch(pattern.substring(1),str.substring(map.get(c).length()));
                    }
                } else {
                    for(int i=1;i<=str.length();i++){  //this char can match any substring from 0 to 1 to 0 to end
                        String newword=str.substring(0,i);
                        if(words.contains(newword)){  //this the new word already been visited, skip
                            continue;
                        }
                        map.put(c,newword);
                        words.add(newword);
                        boolean r = wordPatternMatch(pattern.substring(1),str.substring(map.get(c).length()));
                        if(r) return true; //if this new mapping works, return true, otherwise continue mataching
                        map.remove(c);
                        words.remove(newword);
                    }
                }
            }
            return false;
        }
    }
    

  • 1
    M

    @sse.michael ! Great optimizations.

    You could put s.substring(i) after p.substring(1), since the newWord's length is always i


Log in to reply
 

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