Short Java Solution with Explanation


  • 0
    Y
    public class Solution {
        private HashMap<Character, String> M = new HashMap<>();
        private Set<String> S = new HashSet<>(); // bijection --> one-to-one correspondence between pattern letter and matched substring
        // set stores already matched substrings, so it can't be matched by another pattern
        
        public boolean wordPatternMatch(String pattern, String str) {
            if (pattern.length() == 0 && str.length() == 0) {
                return true;
            }
            // if only one of the "pattern" and "string" is empty while the other is not, return false
            if (pattern.length() == 0 || str.length() == 0) {
                return false;
            }
            char p = pattern.charAt(0);
            if (M.containsKey(p)) {
                // if a pattern matching is found, return true when the rest of string can be matched, otherwise must return false
                if (str.startsWith(M.get(p)) && wordPatternMatch(pattern.substring(1), str.substring(M.get(p).length()))) {
                    return true;
                }
                return false;
            }
            // when pattern is not found, iterate all possible pattern matchings and recursively check if it works
            for (int i = 1; i <= str.length(); i++) {
                if (S.contains(str.substring(0, i))) {
                    continue;
                }
                M.put(p, str.substring(0, i));
                S.add(str.substring(0, i));
                if (wordPatternMatch(pattern.substring(1), str.substring(i))) {
                    return true;
                }
                M.remove(p);
                S.remove(str.substring(0, i));
            }
            return false;
        }
    }
    

Log in to reply
 

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