单词拆分
动态规划
单词就是物品，字符串s就是背包，单词能否组成字符串s，就是问物品能不能把背包装满。
拆分时可以重复使用字典中的单词，说明就是一个完全背包！
dp[i] : 字符串长度为i的话，dp[i]为true，表示可以拆分为一个或多个在字典中出现的单词。
dp[0]初始为true完全就是为了推导公式。
下标非0的dp[i]初始化为false，只要没有被覆盖说明都是不可拆分为一个或多个在字典中出现的单词。
dp[j]=true 来自于 dp[i]=true + 字串s(i，j-i)可以在字典中找到。
例如输入“leetcode” ，dp[ 0 ] 初始化为1 ，
dp[ 4 ] = 1 , 因为 dp[ 0 ] =1 ，字串 s（ 0 ， 4 - 0）即”leet“ 可以在字典找到
dp[ 8 ] = 1 , 因为 dp[ 4 ] =1 ，字串 s（ 4 ， 8 - 4）即”code“ 可以在字典找到
class Solution { public: bool wordBreak(string s, vector<string>& wordDict) { vector<bool> dp(s.size()+1 ,false); unordered_set<string> wordSet(wordDict.begin(), wordDict.end()); dp[0] = true; // dp[j]=true 来自于 dp[i]=true + 字串s(i，j-i)可以在字典中找到。 for(int j = 1 ; j<=s.size() ; j++)//背包尺寸 { for(int i = 0 ; i < j ;i++ )//字串长度 { string word = s.substr( i , j-i ); if(wordSet.find(word) != wordSet.end() && dp[i]==true ) dp[j] = true; } } // for(auto it:dp) cout<<it<<' '; return dp[s.size()]; } };
二刷
回溯（超时）
class Solution { public: bool result = false; vector<string> path; void track_back(string &s, vector<string>& wordDict ,int indnx) { if(result == true) return; if(path.size() != 0) { string tmp; for(int i=0 ; i<path.size();i++) tmp += path[i]; if(tmp.size() > s.size()) return; else if(tmp == s) { result = true; return; } } for(int i=indnx ; i<wordDict.size() ;i++) { path.push_back(wordDict[i]); track_back(s,wordDict,indnx); path.pop_back(); } return; } bool wordBreak(string s, vector<string>& wordDict) { track_back(s,wordDict,0); return result; } };
动态规划
class Solution { public: bool wordBreak(string s, vector<string>& wordDict) { unordered_set<string> wordDict_set(wordDict.begin(),wordDict.end()); vector<bool> dp(s.size()+1 , false); dp[0] = true; for(int j=1 ; j<=s.size() ;j++) { for(int i=0 ; i<j ; i++) { string tmp = s.substr(i,j-i); if(wordDict_set.find(tmp) != wordDict_set.end() && dp[i] == true) dp[j] = true; } } return dp[s.size()]; } };
