?LeetCode刷題實(shí)戰(zhàn)139：?jiǎn)卧~拆分
Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words.
Note:
The same word in the dictionary may be reused multiple times in the segmentation.
You may assume the dictionary does not contain duplicate words.
題意
示例 1：
輸入: s = "leetcode", wordDict = ["leet", "code"]
輸出: true
解釋: 返回 true?因?yàn)?"leetcode"?可以被拆分成 "leet code"。
示例 2：
輸入: s = "applepenapple", wordDict = ["apple", "pen"]
輸出: true
解釋: 返回 true?因?yàn)?"applepenapple"?可以被拆分成 "apple pen apple"。
? 注意你可以重復(fù)使用字典中的單詞。
示例 3：
輸入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
輸出: false
解題
class?Solution?{
public:
????bool?wordBreak(string?s, vector<string>& wordDict)?{
????????vector<int> dp(s.size()+1, 0);
????????dp[0] = 1;
????????unordered_set<string> st(wordDict.begin(), wordDict.end());
????????for(int?i = 1; i <= s.size(); i++)
????????{
????????????for(int?j = 0; j < i; j++)
????????????{
????????????????auto?pos = st.find(s.substr(j, i-j));
????????????????if(dp[j] && pos != st.end())
????????????????{
????????????????????dp[i] = 1;
????????????????????break;
????????????????}
????????????}
????????}
????????return?dp[s.size()];
????}
};