139. Word Break

Description

给出两道题

Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words. You may assume the dictionary does not contain duplicate words.
For example, given
s = “leetcode”,
dict = [“leet”, “code”].
Return true because “leetcode” can be segmented as “leet code”.
Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, add spaces in s to construct a sentence where each word is a valid dictionary word. You may assume the dictionary does not contain duplicate words.
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”].

Solution

第一道题是查看给定字符串s是否可以由wordDict中的子串组成，当然最简单的思路就是暴力了，一个个的比较，这里第二题就是使用该暴力解法，但是显然不应该用这样的方法来做题，而且对于这样的字符串和子串的问题应该第一时间想到的时dp解法
这里dp数组是一个boolean类型的一维数组，dp[i]表示的是第1个字符到第i个字符是否可以由wordDict中的子串组成(i>=1)，初始条件i=0时为true
基本思路：用两个for循环，外层表示如果字符串长度为i时，内层循环对wordDict遍历，如果dp[j]=true，且s[j:i]=word，就表明字符串长度为i时，是可以有wordDict中的子串组成的，因此设置dp[i]=true，并返回，具体代码如下：
参考：java-implementation-using-dp-in-two-ways

public static boolean wordBreak(String s, List<String> wordDict) {
    boolean dp[]=new boolean[s.length()+1];
    dp[0]=true;//初始化
    for(int i=1;i<=s.length();i++){
        for(String word:wordDict){
            if(word.length()<=i){
                if(dp[i-word.length()]){
                    if(word.equals(s.substring(i-word.length(),i))){
                        dp[i]=true;
                        break;
                    }
                }
            }
        }
    }
    return dp[s.length()];
}

第二道题是找出所有可能的组合，刚开始我想套用上面的dp，然后加个Map来解决，后来发现有点麻烦，最后放弃了，用最直接的dfs解决，很简单但很显然是通不过的(TLE)

public List<String> wordBreak(String s, List<String> wordDict) {
    List<String> list=new ArrayList<>();
    dfs(s,0,wordDict,"",list);
    return list;
}
private void dfs(String s, int i, List<String> wordDict, String temp,List<String> list) {
    if(i==s.length()){
        list.add(temp.trim());
    }else {
        for(String word:wordDict){
            if(word.length()<=s.length()-i){
                if(word.equals(s.substring(i,i+word.length()))){
                    dfs(s,i+word.length(),wordDict,temp+" "+word,list);
                }
            }
        }
    }
}

这里给出python的解法，又是同一个人，难懂的代码
参考:9 lines Python, 10 lines C++

def wordBreak(self, s, wordDict):
    memo = {len(s): ['']}
    def sentences(i):
        if i not in memo:
            memo[i] = [s[i:j] + (tail and ' ' + tail)
                       for j in range(i+1, len(s)+1)
                       if s[i:j] in wordDict
                       for tail in sentences(j)]
        return memo[i]
    return sentences(0)

解释一下：tail and ' ' + tail中的and：and从左到右计算表达式，若所有值均为真，则返回最后一个值，若存在假，返回第一个假值。
这的代码先判断s[i:j]是否在wordDict中，如果在就递归sentences(j)，sentences(j)返回的是s[j:]由wordDict组成的不同种方式，然后返回的list的每个元素和s[i:j]进行拼接，得到全部的可能组合

最后，记录这样的题目
126 Word Ladder II
127 Word Ladder
140 Word Break II