Java Backtracking Solution. Can someone help to optimize it?


  • 0
    S
    public boolean wordPatternMatch(String pattern, String str) {
        return helper(pattern, str, 0, 0, new HashMap<Character, String>(), new HashSet<String>());
    }
    private boolean helper(String pattern, String str, int p, int strPosition, HashMap<Character, String> memo, HashSet<String> set){
        if(p == pattern.length() && strPosition == str.length())
            return true;
        else if(p == pattern.length() || strPosition == str.length())
            return false;
        else{
            char c = pattern.charAt(p);
            if(memo.containsKey(c)){
                String pre = memo.get(c);
                if(pre.length() + strPosition > str.length())
                    return false;
                String cur = str.substring(strPosition, strPosition + pre.length());
                if(cur.equals(pre))
                    return helper(pattern, str, p + 1, strPosition + pre.length(), memo, set);
                else
                    return false;
            }else{
                for(int i = strPosition ; i < str.length() ; i++){
                    String temp = str.substring(strPosition, i + 1);
                    if(set.contains(temp))
                        continue;
                    memo.put(c, temp);
                    set.add(temp);
                    if(helper(pattern, str, p + 1, i + 1, memo, set))
                        return true;
                    memo.remove(c);
                    set.remove(temp);
                }
                return false;
            }
        }
            
    }

  • 0
    D

Log in to reply
 

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