题目描述
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".
题解：
/*
题意：
给定一个字符串和词典。输出字符串是否能被分割成一个或多个词典中包含的单词。
思路：
1.原问题满足：
* 最优子结构：问题（s是否可以拆分成多个单词）可以分解为其每个子串是否能拆分为多个单词，如果每个子串都能拆分，则原串也能被拆分。
* 重叠子问题：有一些串会被反复计算是否能拆分
2.动态规划
3.递推关系式：
f(i)表示前i个字符组成的字符串能否拆分成单词
f(i) = f(j) && f(j+1,i) 0<=j<i<=length
*/
#include<unordered_set>
using namespace std;
class Solution {
public:
bool wordBreak(string s, unordered_set<string> &dict) {
int length = s.length();
//dp[i]表示前i个字符可被拆分成单词
vector<bool> dp(length + 1);
dp[0] = true;
for (int pos = 0; pos <= length; pos++) {
for (int i = pos + 1; dp[pos] && i <= length; i++) {
if (dict.find(s.substr(pos, i - pos)) != dict.end()) {
dp[i] = true;
}
}
}
return dp[length];
}
};
