题目描述

题目链接：139. Word Break

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.

例子

例子 1

Input: s = "leetcode", wordDict = ["leet", "code"] Output: true Explanation: Return true because "leetcode" can be segmented as "leet code".

例子 2

Input: s = "applepenapple", wordDict = ["apple", "pen"] Output: true Explanation: Return true because "applepenapple" can be segmented as "apple pen apple". Note that you are allowed to reuse a dictionary word.

例子 3

Input: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"] Output: false

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.

解题思路

这道题可以用记忆化递归的思路来进行求解：

• 对于题目中给出的 "leetcode" 和 ["leet", "code"]，对于一整个单词，我们可以将它分解成不同的子问题来分别求解:
  • "leetcode" --> "l" && "eetcode" 对于这两部分，我们只需要判断 wordbreak("l") && dict.count("eetcode") 是否为真即可，假如为真那么对于整个 "leetcode" 也可以判断为真，否则
  • "leetcode" --> "le" && "etcode" 进行同样操作，注意由于 wordbreak("l") 我们已经进行过一次计算，因此在计算 wordbreak("le") 中时可以利用该结果节省计算时间

代码如下：

#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>

class Solution {
public:
    bool wordBreak(std::string s, std::vector<std::string>& wordDict) {
        std::unordered_set<std::string> dict(wordDict.begin(), wordDict.end());

        return wordBreak(s, dict);
    }

    bool wordBreak(const std::string& word,
                   const std::unordered_set<std::string>& dict) {
        if (m_notes.count(word)) return m_notes[word];

        if (word.empty() || dict.count(word)) return true;

        for (int i = 1; i < word.length(); i++) {
            std::string first = word.substr(0, i);
            std::string second = word.substr(i);
            if (wordBreak(first, dict) && dict.count(second)) {
                m_notes[word] = true;
                return true;
            }
        }

        m_notes[word] = false;
        return false;
    }

private:
    std::unordered_map<std::string, bool> m_notes;
};

• 时间复杂度: O(n^2)
• 空间复杂度: O(n^2)

GitHub 代码同步地址： 139.WordBreak.cpp

其他题目： GitHub: Leetcode-C++-Solution 博客： Leetcode-Solutions