## Sunday, November 23, 2014

### [LeetCode] Word Break I, II

Word Break I

Given a string s and a dictionary of words dict, determine if s can be segmented into a space-separated sequence of one or more dictionary words.
For example, given
s = "leetcode",
dict = ["leet", "code"].
Return true because "leetcode" can be segmented as "leet code".

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"].

dp[i]：S[0:i-1]是否能被break。例如dp[1]表示s[0]是否能被break。
dp[0] = true
dp[i] = true if and only if:
1. 存在一个i-1>=k>=0，使s[k:i-1]存在于dict中。
2. s[0: k-1]可以被break，即dp[k] = true。

 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 class Solution { public: bool wordBreak(string s, unordered_set &dict) { vector dp(s.size()+1,false); dp[0] = true; for(int i=0; i=0; j--) { if(dp[j] && dict.count(s.substr(j,i-j+1))!=0) { dp[i+1] = true; break; } } } return dp[s.size()]; } };

 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 class Solution { public: vector wordBreak(string s, unordered_set &dict) { vector sentences; vector sol; findWordBreak(s, dict, 0, sol, sentences); return sentences; } void findWordBreak(string &s, unordered_set &dict, int start, vector &sol, vector &sentences) { if(start==s.size() && !sol.empty()) { // find word break string temp = sol[0]; for(int i=1; i