My DP solution in JAVA


  • 16
    L
    public class Solution {
        public List<String> wordBreak(String s, Set<String> dict) {
            Map<Integer, List<String>> validMap = new HashMap<Integer, List<String>>();
    
            // initialize the valid values
            List<String> l = new ArrayList<String>();
            l.add("");
            validMap.put(s.length(), l);
    
            // generate solutions from the end
            for(int i = s.length() - 1; i >= 0; i--) {
                List<String> values = new ArrayList<String>();
                for(int j = i + 1; j <= s.length(); j++) {
                    if (dict.contains(s.substring(i, j))) {
                        for(String word : validMap.get(j)) {
                            values.add(s.substring(i, j) + (word.isEmpty() ? "" : " ") + word);
                        }
                    }
                }
                validMap.put(i, values);
            }
            return validMap.get(0);
        }
    }
    

    Basically my idea is the following:

    1. Scan the the string from the tail
    2. Build possible solution for the current index based on DP results
    3. Return the solution when index==0

  • 15
    Z

    Hi, my code is similar with yours except it scans from left to right.
    It TLE on input like this

    "aaaaaaaaaaaaaaaaaaaaaaaaaaaaab"

    Thus, I find your code will TLE on input like this

    "baaaaaaaaaaaaaaaaaaaaaaaaaaaaa"

    Since you got accepted, I suspect the test inputs haven't contain inputs like the second one. :-)

    I think a right code should check sub-strings on both side.

    Good luck!


  • 1
    Z

    yes,me too00ooooooooo


  • 0
    Z

    Hi zdsfwy,

    I also do it from left to right, and get TLE for "aaaaaaaaaaaaaaaab".
    But, I found my problem is that, I forget to update the HashMap.

    After I put the result into the HashMap, it's accepted.


  • 0
    Z

    Can you post your code? I get TLE.


  • 0
    S

    I am having the same issue. I am going form left to right and have a TLE for this particular test case...Pls post code if u have it working !!


  • 0
    Z

    Submission Result: Time Limit Exceeded
    Last executed input: "baaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa


  • 6
    K

    Hi, my code passed the newest test cases. Here's my approach:

    Recursively scan through the array from left to right. At each point, perform a for loop from the current index to the end of the string to see if you can form words along the way. If a word is found, update the current index to the position right after the word, and call the recursive function.

    The key to minimizing time complexity is by keeping a hash set of indexes that are "unbreakable", meaning you cannot break up the words properly from the current index to the end of the string. When we encounter these kind of situations, we know to return and save time. An additional boolean variable "wordFound" is used to keep track of whether or not the remaining substring is "breakable".

        public class Solution {
        public List<String> wordBreak(String s, Set<String> wordDict) {
            List<String> result = new LinkedList<String>();
            wordBreakHelper(new HashSet(), 0,result, s, "", wordDict);
            return result;
        }
        
        public boolean wordBreakHelper(HashSet badIndex, int curIndex, List<String> result, String s, String curSentence, Set<String> wordDict) {
            boolean foundWord = false;
            for(int i = curIndex; i < s.length(); i++) {
                if(wordDict.contains(s.substring(curIndex,i+1))) {
                    String newSentence = curSentence + " " + s.substring(curIndex,i+1);
                    if(i == s.length()-1) {
                        result.add(newSentence.substring(1));
                        foundWord = true;
                    } else {
                        if(badIndex.contains(i+1)) continue;
                        if(wordBreakHelper(badIndex, i+1, result, s, newSentence, wordDict)) foundWord = true;
                    }
                }
            }
            if(foundWord) return true;
            else {
                badIndex.add(curIndex);
                return false;
            }
        }
    }

  • 2
    Y

    Hi, Your code did not pass the test, results in TLE.


  • 0
    A

    Hi, is this backtracking?


Log in to reply
 

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