DP Java solution from Word Break I


  • 0
    T

    This solution is adapted from Word Break I, the inline comment in code should be enough to explain the idea.

    public List<String> wordBreak(String s, Set<String> dict) {
            List<List<String>> results = new ArrayList<>();
            for(int i=0; i<=s.length(); i++)
                results.add(i, null);
            // initial condition
            results.set(s.length(), new ArrayList<String>(Arrays.asList("")));
            
            for(int i=s.length()-1; i>=0; i--){
                for(String dictWord : dict){
                    int size = dictWord.length();
                    // results.get(i+size) != null means there was a hit on (i+size)
                    if(i+size <= s.length() && dictWord.equals(s.substring(i, i+size)) && results.get(i+size) != null){
                        List<String> tempList = results.get(i+size);
                        List<String> newList = new ArrayList<>();
                        // if there are more than 1 hit at index, then append to the old list
                        if(results.get(i) != null)
                                newList = results.get(i);
                        for(String word : tempList){
                            // don't add space if the word only contains ""(the s.length()th element)
                            if(word.length() > 0)
                                newList.add(s.substring(i, i+size) + " " + word);
                            else
                                newList.add(s.substring(i, i+size));
                        }
                        results.set(i, newList);
                    }
                }
            }
            
            if(results.get(0) == null)
                results.set(0, new ArrayList<String>());
                
            return results.get(0);
        }

Log in to reply
 

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