给定字符串s和包含非空单词列表的字典wordDict，请确定s是否可以分隔为一个或多个字典单词的以空格分隔的序列。 C ++解决方案

Example 1:
Input: s = "苹果penapple", wordDict = ["苹果", "pen"]
Output: true
Explanation: "苹果penapple" can be seperated as "苹果 pen 苹果".

这个问题可以通过使用解决 DP [动态编程].

在解释代码之前，我们先看一下代码。

C ++解决方案

#include<iostream>
#include<unordered_set>
#include<vector>
#include<string>

using namespace std;

bool wordBreak(string s, unordered_set<string>& wordDict) 
{
    int n = s.length();
    vector<bool> dp(n + 1, false);
    dp[0] = true;

    for (int i = 1; i <= n; i ++) 
    {
        for (int j = 0; j < i; j ++) 
        {  
        	//cout<<"i = "<< i << " j = "<< j<< " s.substr(j, i - j) = "<< s.substr(j, i - j)<<endl;

            dp[i] =  dp[j] && wordDict.count(s.substr(j, i - j));
            if (dp[i]) {
            	//cout<<"Came to break ======= "<<endl;
            	break;
            }
            
        }
    }

    return dp[n];
}

int main()
{
	string str = "苹果和苹果";
	unordered_set<string> dict = {"苹果", "and"};

	if(wordBreak(str, dict))
		cout<<"Present"<<endl;
	else
		cout<<"Not Present"<<endl;

return 0;
}

输出：

Present

说明：

从上面的代码中，我们使用布尔向量保存真值。

第一个dp [0]设置为true，因为它将帮助我们找到第一个子字符串（如果存在）。

然后，我们开始使用适当的vavlue填充布尔向量dp。

如果dp [i]的值为true，则字典中会出现dp [0] tp dp [i]的子字符串。

然后，我们从dp [i + 1]开始搜索，直到结束。

在我们的示例中s =“appleandapple”和dict = {apple和}

当i = 5时，j = 0，我们得到的单词=“apple”.

我们将设置dp [5] = true。

在循环结束时，布尔向量输出将是：

1 0 0 0 0 1 0 0 1 0 0 0 0 1

可以将其映射到我们的示例，如下图所示：

最后，我们采用dp [string_length]的值得出结果。

该网站上可用的教程列表：