Leetcode 140. Word Break

题目

本题有两个不同难度的版本：139. Word Break 和 140. Word Break II。

139. Word Break

• Difficulty: Medium
• Total Accepted: 263K
• Total Submissions: 798K

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.

Example 1:

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

Example 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.

Example 3:

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

140. Word Break II

• Difficulty: Hard
• Total Accepted: 133K
• Total Submissions: 520K

Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, add spaces in s to construct a sentence where each word is a valid dictionary word. Return all such possible sentences.

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.

Example 1:

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

Example 2:

Input:
s = "pineapplepenapple"
wordDict = ["apple", "pen", "applepen", "pine", "pineapple"]
Output:
[
  "pine apple pen apple",
  "pineapple pen apple",
  "pine applepen apple"
]
Explanation: Note that you are allowed to reuse a dictionary word.

Example 3:

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

解题报告

139. Word Break

AC 截图

题目大意

给出一个非空字符串，判断其是否能够由字典中的单词组成。

解题思路

设置一个布尔数组，对于其中下标为 i 的项，表示从起始字符到第 i 个字符为一个合法子串。其中，下标为 0 初始为 true。通过如下方式更新这个布尔数组：

对于下标为 i 的项，向前遍历布尔数组，如果第 j 项为 true，则判断从 j 到 i 的子字符串是否在字典内。若在字典内，则当前项置 true，退出内循环，并且继续向第 i + 1 项遍历更新。

在遍历完后，我们只需判断最后一项是否为 true 即可。

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

class Solution {
public:
    bool wordBreak(string &s, vector<string> &wordDict) {
      unordered_set<string> dict;
      for (auto &iter: wordDict) dict.insert(iter); 
      return wordBreak(s, dict);
    }

    bool wordBreak(string &s, unordered_set<string> &wordDict) {
      int size = s.size();
      vector<bool> dp(size, false);

      dp[0] = true;
      for (int i = 1; i <= size; ++i) {
        for (int j = i - 1; j >= 0; --j) {
          if (dp[j]) {
            if (wordDict.find(s.substr(j, i - j)) != wordDict.end()) {
              dp[i] = true;
              break;
            }
          }
        }
      }

      return dp[size];
    }
};

140. Word Break II

AC 截图

题目大意

和上题基本一致，但是本题额外要求我们输出所有可能的分割情况。

解题思路

把布尔数组换成一个二维数组。然后在字典内找到当前项的时候，不退出内循环，但是将 j 添加到第 i 项的数组内。最后我们只需要通过这些数组重建字符串即可。

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

static const auto runfirst = []() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    return nullptr;
}();

class Solution {
    vector<vector<int> > dp;

public:
    vector<string> wordBreak(string &s, vector<string> &wordDict) {
      unordered_set<string> dict;
      for (auto &iter: wordDict) dict.insert(iter); 
      int size = s.size();
      dp.resize(size + 1);
      dp[0].push_back(0);
      for (int i = 1; i <= size; ++i) for (int j = i - 1; j >= 0; --j) if (dp[j].size()) if (dict.find(s.substr(j, i - j)) != dict.end()) dp[i].push_back(j);
      return subQuestion(size, s);
    }

    vector<string> subQuestion(int index, string &s) {
      vector<string> result;
      if (index) {
        for (auto &iter : dp[index]) {
          auto strs = subQuestion(iter, s);
          if (strs.empty()) result.push_back(s.substr(0, index));
          else {
            auto substr = s.substr(iter, index - iter);
            for (auto &subResult : strs) result.push_back(subResult + " " + substr);
          }
        }
      } else return vector<string>();

      return result;
    }
};