140. Word Break II.md

140. Word Break II

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. Return all such possible sentences.

Note:

• The same word in the dictionary may be reused multiple times in the segmentation.
• You may assume the dictionary does not contain duplicate words.

Example 1:

Input:
s = "catsanddog"
wordDict = ["cat", "cats", "and", "sand", "dog"]
Output:
[
  "cats and dog",
  "cat sand dog"
]

Example 2:

Input:
s = "pineapplepenapple"
wordDict = ["apple", "pen", "applepen", "pine", "pineapple"]
Output:
[
  "pine apple pen apple",
  "pineapple pen apple",
  "pine applepen apple"
]
Explanation: Note that you are allowed to reuse a dictionary word.

Example 3:

Input:
s = "catsandog"
wordDict = ["cats", "dog", "sand", "and", "cat"]
Output:
[]

Solution

哇自己写出来的hard题目

相比上一题增加一个dfs记录选词的步骤即可

10/29 新增了python code，78%的。

Code

def DFS(index,back,path,result):
    if index == 0:
        result.append(path)
    else:
        for idx in back[index]:
            DFS(idx,back,[idx]+path,result)
            
    
class Solution(object):
    def wordBreak(self, s, wordDict):
        """
        :type s: str
        :type wordDict: List[str]
        :rtype: List[str]
        """
        f = [0 for i in range(len(s))]
        back = [[] for i in range(len(s)+1)]
        f.insert(0,1)
        
        for i in range(len(s)+1):
            for j in range(i):
                if f[j]==1 and s[j:i] in wordDict:
                    f[i] = 1
                    back[i].append(j)
                    
        result = []
        index = len(back)-1
        path = [index]
        DFS(index,back,path,result)
        output = []
        for seq in result:
            res = s[seq[0]:seq[1]]
            for i in range(2,len(seq)):
                res += " " + (s[seq[i-1]:seq[i]])
            output.append(res)
        return output

Code - Java

class Solution {
    List<String> res = new ArrayList<String>();
    private void helper(String s, int st, List<String> path, List<String> res, HashSet<String> set)
    {
        if(st>=s.length())
        {
            res.add(String.join(" ",path));
            return ;
        }
        for(int i=st;i<=s.length();i++)
        {
            if(set.contains(s.substring(st,i)))
            {
                path.add(s.substring(st,i));
                helper(s,i,path,res,set);
                path.remove(path.size()-1);
            }
                
        }
        return;
        
    }
    public List<String> wordBreak(String s, List<String> wordDict) {
        HashSet<String> set = new HashSet(wordDict); 
        // int st = 0;
        helper(s, 0, new ArrayList<String>(), res, set);
        return res;
    }
}

Code

class Solution(object):
    def wordBreak(self, s, wordDict):
        """
        :type s: str
        :type wordDict: List[str]
        :rtype: List[str]
        """
        def helper(s, wordDict, record):
            if not s:
                return []
            if s not in record:
                res = []
                for word in wordDict:
                    if s.startswith(word):
                        if len(word) == len(s):
                            res.append(word)
                        else:
                            result_rest = helper(s[len(word):], wordDict, record)
                            for item in result_rest:
                                item = word + ' ' + item
                                res.append(item)                
                record[s] = res
            # print(s)
            # print(record[s])
            return record[s]
            
        
        record = {}
        return helper(s, wordDict, record)