Word Break
Total Accepted: 22281 Total Submissions: 105657My Submissions
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".
题意：
给定一个字符串和一个单词字典，判断这个字符串是否可以用字典里的单词来分割
思路：dp
设dp[i] 表示字符串[0,i]的子串是否能被字典里的单词来分割
dp[i] = true ,if 存在0 < k < i 使得 dp[k]为true并且字符串[k + 1,i]在单词字典里；或者 字符串[0,i]本身就在单词字典里。
dp[i] = false , else
复杂度：时间O(n)，空间O(n)
bool wordBreak(string s, unordered_set
&dict){
vector
dp(s.size(), false); for(int i = 0; i < s.size(); ++i){ dp[i] = dict.find(s.substr(0, i + 1)) != dict.end(); if(dp[i]) continue; for(int k = 0; k < i; ++k){ if(dp[k] && dict.find(s.substr(k + 1, i - k )) != dict.end()) { dp[i] = true; break; } } } return dp[s.size() - 1]; }