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".
解题思路：
问题： 根据给定的单词字典，判断一个字符串是否可以全部被分割为有效单词。
第一个问题，给定一个字符串， 怎么判断它是不是一个有效单词呢？
本人首先想到是之前做过的 Trie Tree ，打算用 Trie Tree 结构来判断一个字符串是不是一个有效单词。
后来才知道， unordered_set 是 C++ 自带的数据结构，能直接用来检索一个字符串是否为有效单词。囧。看来对 C++ 还不够熟悉。
值得一提的是，用 Trie Tree 实现的算法也通过了 LeetCode 的测试，当然，unordered_set 的完成效率更快。
第二个问题，如何判断一个字符串是否可以全部被分割为有效单词，即原问题。
假设将字符串 s 分割为两段，[0,i-1], [i, n-1]，如果[0, i-1] 为有效单词，[i, n-1]为有效单词集合，那么 s 就是一个有效字符串。
将 i 从 1 到 n-1 遍历一次，求得 s 是否是一个有效字符串。
第三个问题，效率满，出现很多反复求解的子问题。
DP思路，即表格法，记录已计算结果。
vector<int> v;
bool isMatch(string s, unordered_set<string>& wordDict){
unordered_set<string>::iterator us_iter = wordDict.find(s);
if (us_iter != wordDict.end()) {
return true;
}
for (int i = ; i < s.size(); i++) {
string leftS = s.substr(, i);
unordered_set<string>::iterator leftS_iter = wordDict.find(leftS);
if (leftS_iter != wordDict.end()) {
bool isWordR;
if (v[i] != -) {
isWordR = v[i];
}else{
isWordR = isMatch(s.substr(i, s.size() - i), wordDict);
v[i] = isWordR;
}
if (isWordR) {
return true;
}
}
}
return false;
}
bool wordBreak(string s, unordered_set<string>& wordDict) {
vector<int> tmp(s.size(), -);
v = tmp;
bool res = isMatch(s, wordDict);
return res;
}