Documented backtracking


  • 1
    J
    
    class Solution {
        /*  start: start index in the current cut, < str.length;
            cuts: number of cuts done, stop at pattern's legnth - 1.
            str: original str.
            pats: original pattern converted to char[].
            p2s: contains mapping from pattern to word. 
            s2p: contains mapping from word to pattern.
            Heuristics: pattern's length - 1 is the total cuts needs to be done. if (total cuts - current cuts  >= str.length - (start - 1))  return false;
            returns: if pattern starting from cuts, and str starting from start, match.
        */
        
        private boolean wordPatternMatchHelper(int start, int cuts, String str, char[] pats, HashMap<Character, String> p2s, HashMap<String, Character> s2p)     {
            int numRemainingChars = str.length() - start;
            int totalcut = pats.length - 1;
            if (cuts == pats.length) {
                return true;
            }
            if (totalcut - cuts >= numRemainingChars) {
                return false;
            }
            
            char pat = pats[cuts];
            boolean result = false;
            for (int end = (cuts == pats.length - 1) ? str.length() - 1: start; end < str.length(); end++) {
                String word = str.substring(start, end + 1);
                if (p2s.containsKey(pat)) {
                    if (p2s.get(pat).equals(word)) {
                        result = wordPatternMatchHelper(end + 1, cuts + 1, str, pats, p2s, s2p);
                        if (result == true) {
                            break;
                        }
                    } else {
                        continue;
                    }
                } else {
                    if (s2p.containsKey(word)) {
                        continue;
                    } else {
                        p2s.put(pat, word);
                        s2p.put(word, pat);
                        result = wordPatternMatchHelper(end + 1, cuts + 1, str, pats, p2s, s2p);
                        if (result == true) {
                            break;
                        } else {
                            p2s.remove(pat);
                            s2p.remove(word);
                        }
                    }
                }
            }
            
            return result;
        }
        
        public boolean wordPatternMatch(String pattern, String str) {
            if (str.length() == 0 && pattern.length() == 0) {
                return true;
            } else if (str.length() == 0 || pattern.length() == 0) {
                return false;
            }
            HashMap<Character, String> p2s = new HashMap<>();
            HashMap<String, Character> s2p = new HashMap<>();
            char[] pats = pattern.toCharArray();
            return wordPatternMatchHelper(0, 0, str, pats, p2s, s2p);
        }
    }
    

Log in to reply
 

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