Java Solution using backtracking(similar to Word Pattern I)


  • 0

    This solution is very similar to Word Pattern I, the only different is that we do not know the length of each word in str, so we use for loop to extract potential word to be compared with pattern. Do not forget to restore HashMap and HashSet if the potential word is wrong.

    public boolean wordPatternMatch(String pattern, String str) {
            Map<Character, String> map = new HashMap<>();
            Set<String> set = new HashSet<>();
            return wordPatternMatchHelper(map, set, pattern, str, 0, 0);
        }
        
        public boolean wordPatternMatchHelper(Map<Character, String> map, Set<String> set,
                                              String pattern, String str, int patternIndex, int strIndex) {
            if(patternIndex == pattern.length() && strIndex == str.length()) return true;
            if(patternIndex == pattern.length() || strIndex == str.length()) return false;
    
            boolean res = false;
            for(int i=strIndex; i<=str.length()-(pattern.length()-patternIndex); i++) {
                String currStr = str.substring(strIndex, i+1);
                char currPattern = pattern.charAt(patternIndex);
                if(map.containsKey(currPattern)) {
                    if(map.get(currPattern).equals(currStr)) {
                        res |= wordPatternMatchHelper(map, set, pattern, str, patternIndex+1, i+1);
                        if(res) return res;
                    }
                } else {
                    if(!set.contains(currStr)) {
                        map.put(currPattern, currStr);
                        set.add(currStr);
                        res |= wordPatternMatchHelper(map, set, pattern, str, patternIndex+1, i+1);
                        if(res) {
                            return res;
                        } else {
                            map.remove(currPattern);
                            set.remove(currStr);
                        }
                    }
                }
            }
            return false;
        }
    

Log in to reply
 

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