Word Break II

Given a string s and a dictionary of words dict, add spaces in s to construct a sentence where each word is a valid dictionary word.

Return all such possible sentences.

For example, given
s = "catsanddog",
dict = ["cat", "cats", "and", "sand", "dog"].

A solution is ["cats and dog", "cat sand dog"].

Analysis

• 1st for loop used for avoid TLE for case "aaaa....aab", [a, aa, aaa, aaaaa...]
• 我理解的原因：下面开始是从头开始扫，对于上面的例子，是最后一个字母不match。上面的loop从尾开始扫一遍就可以免除例子。

Code

public class Solution {
    public List<String> wordBreak(String s, Set<String> dict) {
        List<String> res = new ArrayList<String>();

        //important to add ""
        if (s.isEmpty()) {res.add(""); return res;}

        //for loop checking to reduce run time
        for (int j=s.length()-1; j>=0; j--){
            if(dict.contains(s.substring(j))) break;
            else {
                if (j==0) return res;
            }
        }

        //do real work here: for loop to extract 1st word, recursively call on remaining words
        for (int i=1; i<=s.length(); i++){
            if (dict.contains(s.substring(0,i))) {
                List<String> list = wordBreak(s.substring(i), dict);
                for (String str: list){
                    res.add((s.substring(0,i) + " "+ str).trim()); //important to trim
                }
            }
        }

        return res;
    }
}

Reference

Leetcode

• 1st for loop checking adapted from ref
• 2nd for loop wrote by myself, better than ref