LeetCode 139.Word Break (单词拆分)

缺乏、安全感 2022-05-08 10:06 199阅读 0赞

题目描述：

给定一个**非空**字符串 *s* 和一个包含**非空**单词列表的字典 *wordDict*，判定 *s* 是否可以被空格拆分为一个或多个在字典中出现的单词。

**说明：**

*  拆分时可以重复使用字典中的单词。
 *  你可以假设字典中没有重复的单词。

**示例 1：**

输入: s = "leetcode", wordDict = ["leet", "code"]
    输出: true
    解释: 返回 true 因为 "leetcode" 可以被拆分成 "leet code"。

**示例 2：**

输入: s = "applepenapple", wordDict = ["apple", "pen"]
    输出: true
    解释: 返回 true 因为 "applepenapple" 可以被拆分成 "apple pen apple"。
         注意你可以重复使用字典中的单词。

**示例 3：**

输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
    输出: false

AC C++ Solution:

解题思路：

使用布尔向量dp \[\]，如果有效单词(单词序列)在i位置结束，则dp \[ i \]设置为true。  
从当前位置i回看仅查找子串并在dp \[ j \] == true的后一位置查找字典。

代码：

class Solution {
    public:
        bool wordBreak(string s, vector<string>& wordDict) {
            if(wordDict.size() == 0)    return false;
            unordered_set<string> dict(wordDict.begin(),wordDict.end());
            
            vector<bool> dp(s.size()+1,false);
            dp[0] = true;
            
            for(int i = 1; i <= s.size(); i++) {
                for(int j = i-1; j >=0; j--) {  
                    if(dp[j]) {                                     //仅在dp[j]=true的后一位置开始查找字典
                        string word = s.substr(j,i-j);              //在字典中查找子串s[j..i]
                        if(dict.find(word) != dict.end()) {
                            dp[i] = true;
                            break;
                        }
                    }
                }
            }
            
            return dp[s.size()];                //dp最后一位如果是true，则代表整个序列都是可拆分的
        }
    };