java dfs and pruning with dp beats 99.69%(7 ms)


  • 0
    X
        /**
         * @param s a string
         * @param wordDict a set of words
         */
        List<String> rst = new ArrayList<>();
        boolean[] f;
        String s;
        List<String> wordDict;
        int l;
    
        public List<String> wordBreak(String s, List<String> wordDict) {
            // Write your code here
            if (s == null || s.length() == 0 || wordDict == null) {
                return rst;
            }
            int len = s.length();
            this.f = new boolean[len + 1];
            this.s = s;
            this.wordDict = wordDict;
            this.l = s.length();
            int maxLength = 0;
            for (String st : wordDict) {
                int length = st.length();
                maxLength = Math.max(maxLength, length);
            }
            f[len] = true;
            for (int i = len - 1; i >= 0; i--) {
                for (int j = i; j - i < maxLength && j < len; j++) {
                    f[i] = false;
                    if (f[j + 1] && wordDict.contains(s.substring(i, j + 1))) {
                        f[i] = true;
                        break;
                    }
                }
            }
            dfs(0, "");
            return rst;
        }
        void dfs(int pos, String str) {
            if (pos == l) {
                str = str.substring(0, str.length() - 1);
                rst.add(str);
                return;
            }
            if (!f[pos]) {
                return;
            }
            for (int i = pos; i < l; i++) {
                String curtS = s.substring(pos, i + 1);
                if (wordDict.contains(curtS)) {
                    dfs(i + 1, str + curtS + " ");
                }
            }
        }
    }

Log in to reply
 

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