首页 > 代码库 > LeetCode: Word Break
LeetCode: Word Break
LeetCode: Word Break
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".
地址：https://oj.leetcode.com/problems/word-break/
算法：显然，这一道动态规划的题目。用数组dp来存储每一个子问题，其中dp[i]表示在从0到i（包括i）的字串是否能够由字典组成。那么dp[i+1]的解就可以表示成：是否存在一个j(0<=j<=i+1)使得dp[j]为真且从j+1到i+1的字串在字典中。代码如下：
1 class Solution { 2 public: 3 bool wordBreak(string s, unordered_set<string> &dict) { 4 if(s.empty()) return false; 5 int len = s.size(); 6 unordered_set<string>::iterator end_it = dict.end(); 7 vector<bool> dp(len); 8 if(dict.find(s.substr(0,1)) != end_it){ 9 dp[0] = true;10 }else{11 dp[0] = false;12 }13 for(int i = 1; i != len; ++i){14 if(dict.find(s.substr(0,i+1)) != end_it){15 dp[i] = true;16 continue;17 }18 int j = 0;19 while(j<i && (!dp[j] || dict.find(s.substr(j+1,i-j)) == end_it)) ++j;20 dp[i] = (j < i);21 }22 return dp[len-1];23 }24 };
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"].
地址：https://oj.leetcode.com/problems/word-break-ii/
算法：第二题与第一题不同的是，第二题需要构造出所有可能的解，这样的话，我们就必须把每个子问题的所有解情况都存储起来。用一个二维数组dp来存储每一个子问题的解，其中dp[i]存储了所有满足条件的j。最后利用递归的方法构造出所有的解，看代码应该会比说的更清楚吧：
1 class Solution { 2 public: 3 vector<string> wordBreak(string s, unordered_set<string> &dict) { 4 int n = s.size(); 5 if (n < 1) return vector<string>(); 6 vector<vector<int> > dp(n); 7 unordered_set<string>::iterator end_it = dict.end(); 8 if (dict.find(s.substr(0,1)) != end_it){ 9 dp[0].push_back(0);10 }11 for(int i = 1; i != n; ++i){12 if (dict.find(s.substr(0,i+1)) != end_it){13 dp[i].push_back(0);14 }15 for (int j = i-1; j >= 0; --j){16 if (!dp[j].empty() && dict.find(s.substr(j+1,i-j)) != end_it){17 dp[i].push_back(j+1);18 }19 }20 }21 return constructResult(s,dp,n);22 }23 vector<string> constructResult(string &s, vector<vector<int> > &dp,int n){24 if(n < 1)25 return vector<string>();26 vector<int>::iterator it = dp[n-1].begin();27 vector<string> result;28 for (; it != dp[n-1].end(); ++it){29 if (*it == 0){30 result.push_back(s.substr(0,n));31 continue;32 }33 vector<string> temp = constructResult(s,dp,*it);34 vector<string>::iterator str_it = temp.begin();35 for(; str_it != temp.end(); ++str_it){36 result.push_back(*str_it + " " + s.substr(*it,n-(*it)));37 }38 }39 return result;40 }41 };
LeetCode: Word Break