Java solution with key notes


  • 0
    A

    Thanks for the discussion in jeantimex's sharing answer.

    https://leetcode.com/discuss/63252/share-my-java-backtracking-solution

    My implementation after referring those discussion.

    public boolean wordPatternMatch(String pattern, String str) {
        if (pattern == null && str == null) {
            return true;
        }
        if (pattern == null || str == null) {
            return false;
        }
        HashMap<Character, String> map = new HashMap<Character, String>();
        HashSet<String> used = new HashSet<String>();
        return searchPath(pattern, str, 0, 0, map, used);
    }
    
    
    private boolean searchPath(String pattern, String str, int i, int j, HashMap<Character, String> map, HashSet<String> used) {
        /*success base case*/
        if (i == pattern.length() && j == str.length()) {
            return true;
        }
        if (i == pattern.length() || j == str.length()) {
            return false;
        }
        char p = pattern.charAt(i);
        /*If the pattern.charAt(i) has already been mapped.*/
        if (map.containsKey(p)) {
            String word = map.get(p);
            /*It is impossible to meet the success base case along this search path. This search path could be cut off.*/
            if (!str.startsWith(word, j)) {
                return false;
            }
            /*Go deeper for search*/
            return searchPath(pattern, str, i + 1, j + word.length(), map, used);
        } else {
            for (int k = j; k < str.length(); k++) {
                String temp = str.substring(j, k + 1);
                /*Same as WordPattern 1. If the word has already been mapped with other p.*/
                if (!used.contains(temp)) {
                    map.put(p, temp);
                    used.add(temp);
                    /*Once there there is a search path meet the success base case*/
                    if (searchPath(pattern, str, i + 1, j + temp.length(), map, used)) {
                        return true;
                    }
                    used.remove(temp);
                    map.remove(p);
                }
            }
            /*none of "str.substring(j, k + 1)" is qualified*/
            return false;
        }
    }

Log in to reply
 

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