20-lines concise Java solution with explanation


  • 0

    Explanation

    The basic idea is to get permutations by chars in str, pruning the useless branches by pattern check. I used hashMap to store the indexes of str and pattern, if they equal correspondingly, then they should be fully matched. Thanks for StefanPochmann's index comparison method. Any advice will be welcome!

    public boolean wordPatternMatch(String pattern, String str) {
        if (pattern.length() == 0) return (str.length() == 0);
        return dfs(str.toCharArray(), 0, pattern.toCharArray(), 0, "", new HashMap<>());        
    }
    
    boolean dfs(char[] str, int strIndex, char[] pattern, int patterIndex, String current, Map map) {       
       if (strIndex > str.length - 1) return (patterIndex == pattern.length) ;
       if (patterIndex == pattern.length) return (strIndex > str.length - 1) ;
    
        String s = current + str[strIndex];  
    
        // Check if str matches pattern
        Object oldPattern = map.put(pattern[patterIndex], patterIndex), oldStr = map.put(s, patterIndex);      
        if (Objects.equals(oldPattern, oldStr)) {          
            boolean matched = dfs(str, strIndex + 1, pattern, patterIndex + 1, "", map); 
            if (matched) 
                return matched;
        }       
        // Restore the previous values to map.
        map.put(pattern[patterIndex], oldPattern); map.put(s, oldStr); 
    
        // Check the remaining chars in str.
        return dfs(str, strIndex + 1, pattern, patterIndex, current + str[strIndex], map);
    }
    

Log in to reply
 

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