Java Solution DP + DFS (Beats 91.10%)


  • 0
    public class Solution {
        private Set<String> wordDict;
        public List<String> wordBreak(String s, Set<String> wordDict) {
            List<String> result = new ArrayList<String>();
            if (s.length() == 0 || wordDict.size() == 0) {
                return result;
            }
            this.wordDict = wordDict;
            int maxLength = 0;
            for (String str : wordDict) {
                maxLength = Math.max(maxLength, str.length());
            }
            boolean[] possible = new boolean[s.length() + 1];
            possible[0] = true;
            for (int i = 1; i <= s.length(); i++) {
                for (int j = i; j > 0 && i - j + 1 <= maxLength; j--) {
                    if (possible[j - 1] && wordDict.contains(s.substring(j - 1, i))) {
                        possible[i] = true;
                        break;
                    }
                }
            }
            System.out.println(possible[s.length()]);
            if (!possible[s.length()]) {
                return result;
            }
            List<String> list = new ArrayList<String>();
            helper(s, 0, possible, list, result);
            return result;
        }
        
        private void helper(String s, int index, boolean[] possible, List<String> list, List<String> result) {
            if (index == s.length()) {
                StringBuilder sb = new StringBuilder();
                for (String str : list) {
                    sb.append(str);
                    sb.append(" ");
                }
                sb.deleteCharAt(sb.length() - 1);
                result.add(sb.toString());
                return;
            }
            if (!possible[index]) {
                return;
            }
            for (int i = index; i < s.length(); i++) {
                if (!wordDict.contains(s.substring(index, i + 1))) {
                    continue;
                }
                list.add(s.substring(index, i + 1));
                helper(s, i + 1, possible, list, result);
                list.remove(list.size() - 1);
            }
        }
    }
    

  • 0
    A

    I am not able to understand why it should be fast.
    you are scanning that it is possible it insert space or not with O(n^2), if yes then you again recurse with O(n^2). I am using the single loop for this but getting TLE.


  • 0

    @ajak6 Dynamic Programming can prevent us from searching the same intermediate state again and again. Think of one simple input "aaaaaaa...(a lot of a)..aaaaa", you can println the intermediate result and take a look at it. And then you will find using only single DFS is a waste.
    Time complexity of DP is O(mn) in which m is the max string length is dict and n is the size of dict and space complexity is O(m) m is the size of string.
    So in total, the time complexity would be O(m
    n^2). However, with result saved in dp array, we can stop early in search when we find it is impossible.
    Also you can check these posts to find more information.
    https://discuss.leetcode.com/topic/17841/getting-rid-of-tle/2
    https://discuss.leetcode.com/topic/8007/please-add-test-case-baaaaaaaa-aaaa-a-aa-aaa-aaa-aa/3
    And you can also provided your code here and I am glad to take a look.


Log in to reply
 

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