Leetcode: Word Break
Leetcode: Word Break
卡尔曼和玻尔兹曼谁曼
发布于 2019-01-22 16:00:37
发布于 2019-01-22 16:00:37
题目： 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”.
思路分析： 按照官方的解法：动态规划（Dynamic Programming） 感觉自己对动态规划问题还是不能熟练应对。不能准确找出变量之间的递推关系。 设F(0, i)表示前i个子串分割后是否存在于字典中。那么，这道题中存在这样的递推关系：F(0, i) = F(0, j) + F(j, i)，即前i个字符结果为true的充分条件是前j个字符结果为true，第j到i个子串结果也是true。
C++参考代码：
class Solution
{
public:
bool wordBreak(string s, unordered_set<string> &dict)
{
string::size_type size = s.size();
//申请size+1大小的空间，第一个设为true
vector<bool> matches(size + 1, false);
matches[0] = true;
for (size_t i = 1; i <= size; ++i)
{
for (size_t j = 0; j < i; ++j)
{
if (matches[j] && (dict.count(s.substr(j, i - j)) > 0))
{
matches[i] = true;
break;
}
}
}
return matches[size];
}
};C#参考代码：
public class Solution
{
public bool WordBreak(string s, ISet<string> dict)
{
bool[] matches = new bool[s.Length + 1];
matches[0] = true;
for (int i = 1; i <= s.Length; ++i)
{
for (int j = 0; j < i; ++j)
{
if (matches[j] && dict.Contains(s.Substring(j, i - j)))
{
matches[i] = true;
break;
}
}
}
return matches[s.Length];
}
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2015年04月06日，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读