Java 3ms backtrack solution


  • 0
    H
    private boolean res = false;
        private String[] dict;	//pattern dictionary
        private Set<String> set;	//set make sure no two pattern char point to same string
        private char[] pattern;		
        private char[] str;
        private int pl;
        private int sl;
        public boolean wordPatternMatch(String pattern, String str) {
            if (pattern.isEmpty() || str.isEmpty()) return pattern.isEmpty() && str.isEmpty();
            dict = new String[26];
            set = new HashSet<>();
            this.pattern = pattern.toCharArray();
            this.str = str.toCharArray();
            pl = pattern.length();
            sl = str.length();
            dfs(0, 0);
            return res;
        }
        private void dfs (int strPos, int patternPos) {
            if (strPos == sl || patternPos == pl || res) {
                if (strPos == sl && patternPos == pl) res = true;
            } else {
                int cur = pattern[patternPos]-'a';
                for (int i = strPos; sl-i >= pl-patternPos; i++) {
                    String key = new String(str, strPos, i-strPos+1);
                    if (dict[cur] == null) {
                        if (set.add(key)) {
                            dict[cur] = key;
                            dfs (i+1, patternPos+1);
                            dict[cur] = null;
                            set.remove(key);
                        }
                    } else {
                        if (dict[cur].equals(key)) dfs (i+1, patternPos+1);
                    }
                }
            }
        }
    

Log in to reply
 

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