Simple Backtrack Java Solution!


  • 0
    S
    public class Solution {
        public boolean wordPatternMatch(String pattern, String str) {
            if (str.length() < pattern.length()) {
                return false;
            }
            Map<Character, String> map = new HashMap();
            return backtrack(pattern, str, 0 , 0, map);
        }
        
        private boolean backtrack(String pattern, String str, int start1, int start2, Map<Character, String> map) {
            if (start1 == pattern.length() || start2 == str.length()) {
                return start1 == pattern.length() && start2 == str.length();
            }
            if (map.containsKey(pattern.charAt(start1))) {
                if (!str.startsWith(map.get(pattern.charAt(start1)), start2)) {
                    return false;
                }
                int len = map.get(pattern.charAt(start1)).length();
                return backtrack(pattern, str, start1 + 1, start2 + len, map);
            }
            for (int i = start1; i < pattern.length(); i++) {
                if (i > start1 && !map.containsKey(pattern.charAt(start1))) {
                    return false;
                }
                char ch = pattern.charAt(i);
                for (int j = start2; j < str.length(); j++) {
                    String val = str.substring(start2, j + 1);
                    if (!map.containsValue(val)) {
                        map.put(ch, val);
                        if (backtrack(pattern, str, i + 1, j + 1, map)) {
                            return true;
                        }
                        map.remove(ch);
                    }
                }
            }
            return false;
        }
    }
    

Log in to reply
 

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