Naive solution


  • 0
    X

    Test all prefixes of string to the first variable in the pattern if it has not been assigned. Check rest pattern against rest of the string with the assignments.
    If the number of variables in the pattern is m and length of the string is n, space is just the variable assignments O(m + n). Total possible assignments number is O(n^k), each assignment checking is O(n), so worst time is O(n^(k+1)).
    Java implementation:

    import java.util.HashMap;
    import java.util.Map;
    
    public class WordPattern {
        public static boolean match(String pattern, String str) {
            return matchSubstr(pattern, str, new HashMap<>());
        }
    
        private static boolean matchSubstr(String pattern, String str, Map<Character, String> assign) {
            if (pattern.length() == 0)
                return str.length() == 0;
    
            if (str.length() == 0)
                return false;
    
            char ch = pattern.charAt(0);
            String val = assign.get(ch);
            if (val != null) {
                if (!str.startsWith(val))
                    return false;
                return matchSubstr(pattern.substring(1), str.substring(val.length()), assign);
            }
            for (int end = 1; end <= str.length(); end++) {
                Map<Character, String> newAssign = new HashMap<>();
                newAssign.putAll(assign);
                newAssign.put(ch, str.substring(0, end));
                if (matchSubstr(pattern.substring(1), str.substring(end), newAssign))
                    return true;
            }
            return false;
        }
    
        public static void main(String[] args) {
            for (String[] patStr: new String[][]{
                    {"abab",  "redblueredblue"},
                    {"aaaa", "asdasdasdasd"},
                    {"aabb", "xyzabcxzyabc"}
            }) {
                String pat = patStr[0];
                String str = patStr[1];
                System.out.println("Pattern: " + pat + " String: " + str);
                System.out.println("Matched: " + match(pat, str));
            }
        }
    }
    
    

Log in to reply
 

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