LeetCode 139: 单词拆分

[guodongxiaren]

https://leetcode-cn.com/problems/word-break

给定一个非空字符串 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

[guodongxiaren]

BFS

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict)
    {
        // 使用s.substr(i,len)的方式来保存字符串，列表里面保存起始位置i
        list<int> q;
        vector<bool> visited(s.size()+1, false);
        // 放入空字符串
        q.push_back(0);
        visited[0] = true;;

        while (!q.empty()) {
            // 每一层作为一个完整过程进行处理
            int levelSize = q.size();
            for (int i = 0; i < levelSize; ++i) {

                int start = q.front();
                q.pop_front();

                for (const auto& nextWord : wordDict) {

                    int len = nextWord.length();
                    // 当前的单词比原始单词还要长，则直接处理下一个
                    if (s.length() < start + len) {
                        continue;
                    }

                    // 可以拼接成原始单词
                    if (nextWord == s.substr(start)) {
                        return true;
                    }

                    if (visited[start+len]) {
                        continue;
                    }
                    // 如果符合条件，则放入列表中
                    if (s.substr(start, len) == nextWord) {
                        q.emplace_back(start+len);
                        visited[start+len] = true;
                    }
                }
            }
        }

        return false;
    }
};

作者：dou-ya-cai-6 链接：https://leetcode-cn.com/problems/word-break/solution/cyan-du-you-xian-sou-suo-fang-fa-ti-jie-ji-bai-80d/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

[guodongxiaren]

动态规划

bool wordBreak(string s, vector<string>& wordDict) {
    size_t validEnd = 0;
    vector<bool> dp(s.size() + 1, false);
    dp[0] = true;
    for (size_t i = 0; i < s.size(); i++) {
        if (i == validEnd + 1) return false;
        if (!dp[i]) continue;
        for (auto& word : wordDict) {
            size_t newEnd = i + word.size();
            if (newEnd > s.size()) continue;
            if (memcmp(&s[i], &word[0], word.size()) == 0) {
                dp[newEnd] = true;
                validEnd = max(validEnd, newEnd);
            }
        }
    }
    return dp.back();
}

作者：ikaruga 链接：https://leetcode-cn.com/problems/word-break/solution/139-by-ikaruga/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。