单词拆分 C++ 2021-07-01
发布时间
阅读量：
阅读量
若[j, i]这一区间所对应的子串存在于字典中，并且dp[j]的值为真，则可以得出dp[i]的值也为真，这一关系可通过递推公式进行表达。
class Solution {//时间O(n^3) 空间O(n)
public:
bool wordBreak(string s, vector<string>& wordDict)
{
int len = s.size();
unordered_set<string> wordSet(wordDict.begin(), wordDict.end());//便于查找有没有出现在字典里
vector<bool> dp(len + 1, 0);//bool算是个优化 一般就写Int了
dp[0] = 1;
for (int i = 1; i <= len; ++i)
{
for (int j = 0; j < i; ++j)
{全部评论 (0)
还没有任何评论哟~