C++算法-动态规划2

第 4 题 字符串分割 (Word Break)

• 难度: Medium
• 备注：出自 leetcode
• 题目描述
  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".
        bool wordBreak (string s, unordered_set &dict)
        来源：牛客 - leetcode

题目描述
给定一个字符串和一个词典 dict，确定 s 是否可以根据词典中的词分成一个或多个单词。
比如，给定
s = "leetcode"
dict = ["leet", "code"]
返回 true，因为 "leetcode" 可以被分成 "leet code"

#include <bits/stdc++.h>
using namespace std;
bool wordBreak (string s, unordered_set<string> &dict) {//unordered_set &dict 哈希表 //边界判断 if(s.empty())return false;int len=s.size();//vector构造函数实现初始化 vector<bool> canBreak(len+1,false);//初始化 F(0)=truecanBreak[0]=true;for(int i=1;i<=len;i++){//转移方程 F(i)  j<i && F(j) && [j+1,i]for(int j=i-1;j>=0;j--){if(canBreak[j]&&dict.find(s.substr(j,i-j))!=dict.end()){canBreak[i]=true;break;}} }//返回结果 F(s.size()) return canBreak[len];
}
int main() {string s="leetcode";unordered_set<string> dict={"leet","code"};cout<<wordBreak(s,dict);return 0;
}