3ms Java. Beats 99.5%


  • 0
    K

    DP+DFS. And the for loop does not always need to start from 1.

    public class Solution {
        int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
        private void DFS(List<String> res, StringBuilder path, int start, String s, Set<String>wordDict, int []b) {
            if (start >= s.length()) {
                res.add(path.substring(0, path.length() - 1));
                return;
            }
            /* there is no need to start from 1 every time */
            for (int len = min; len <= max && len + start <= s.length(); len++) {
                if ((b[len + start] == 1) || !wordDict.contains(s.substring(start, start + len))) continue;
                int prevend = path.length();
                int presize = res.size();
                path.append(s.substring(start, start + len) + " ");
                DFS(res, path, start + len, s, wordDict, b);
                if (presize == res.size()) {
                    b[len + start] = 1;
                }
                path.delete(prevend, path.length());
            }
        }
        
        public List<String> wordBreak(String s, Set<String> wordDict) {
            List<String> res = new ArrayList<String>();
            StringBuilder path = new StringBuilder();
            int []breakable = new int [s.length() + 1];
            for (String i : wordDict) {
                if (i.length() < min) {
                    min = i.length();
                }
                if (i.length() > max) {
                    max = i.length();
                }
            }
            
            DFS(res, path, 0, s, wordDict, breakable);
            return res;
        }
    }
    

Log in to reply
 

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