单词拆分
作者:Lew's Personal Blog 发布于:2019-12-26 15:49 Thursday 分类:Leetcode
- 给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict,判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。
- 说明:
- 拆分时可以重复使用字典中的单词。
- 可假设字典中没有重复的单词。
示例1
输入: s = "leetcode", wordDict = ["leet", "code"]输出: true
解释: 返回 true
因为 "leetcode" 可以被拆分成 "leet code"。
测试源代码
#include <string>
#include <iostream>
#include <vector>
using namespace std;
bool wordBreak(string& s, vector<string>& wordDict)
{
vector<int> dp(s.size() + 1, 0);
dp[0] = 1;
for (int i = 0; i <= s.size(); ++i)
{
for (auto word : wordDict)//进行遍历
{
int ws = word.size();
if (i - ws >= 0)
{
int cur = s.compare(i - ws, ws, word);//掉用compare函数
if (cur == 0 && dp[i - ws] == 1)
{
dp[i] = 1;
}
}
}
}
return dp[s.size()];
}
int main(int argc, char **argv)
{
string s = "leetcofe";
cout << "the length of s: " << s.size() << endl;
vector<string> wordDict = { "leet", "code" }; //字符串数组
cout << wordBreak(s, wordDict) << endl;
return 0;
}
标签: C++
« 上一篇 队列 | leetcode测试代码 下一篇»