Super easy understand backtracking JAVA Solution


  • 0
    A
    public class Solution {
        boolean result = false;
        public boolean wordPatternMatch(String pattern, String str) {
            HashMap<Character, String> hm = new HashMap<Character, String>();
            HashSet<String> hs = new HashSet<String>();
            helper(pattern, str, hm, hs, 0, 0, 0);
            return result;
        }
        void helper(String pattern, String str, HashMap<Character, String> hm, HashSet<String> hs, int s, int e, int count) {
            if (result) {
                return;
            }
            if (e == str.length() && count == pattern.length()) {
                result = true;
                return;
            } 
            if (e == str.length() || count == pattern.length()) {
                return;
            } 
            char curPat = pattern.charAt(count);
            String curStr = str.substring(s, e + 1);
            // 1. if the length of the cur word is right;
            if (!hm.containsKey(curPat)) {
                if (!hs.contains(curStr)) {
                    hm.put(curPat, curStr);
                    hs.add(curStr);
                    helper(pattern, str, hm, hs, e + 1, e + 1, count + 1); 
                    hm.remove(curPat);
                    hs.remove(curStr);
                }
            } else {
                if (hm.get(curPat).equals(curStr)) {
                    helper(pattern, str, hm, hs, e + 1, e + 1, count + 1); 
                }
            }
            // if the length of the cur word is wrong;
            helper(pattern, str, hm, hs, s, e + 1, count); 
        }
    }

Log in to reply
 

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