Word Break I, II

相关题目:

Word Break, 一开始打算用 Backtracking 做, 但是 TLE 了. 折腾了许久, 才发现这题本质上是搜索, 存在重复的搜索状态, 遂用 DP 来解.

还有一题简单的 follow up: Word Break II. 解题思路类似, 只不过是加上了中间状态的保存:

  1. dp[i]: a list of indices j where (i, j) is the prefix word of a valid spaced-seperated sentence.
  2. 从后往前 DP, 构建 (1) 的数组, 然后再从前往后 DFS, 生成 sentance.
// Word Break
class Solution {  
public:  
  bool wordBreak(string s, unordered_set<string> &wordDict) {
    const int n = s.size();
    vector<bool> dp(n, false);
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j <= i; ++j) {
        auto word = s.substr(j, i + 1 - j);
        bool pre_state = (j > 0 ? dp[j - 1] : true);
        if (wordDict.count(word) > 0 && pre_state) {
          dp[i] = true;
          break;
        }
      }
    }
    return dp.back();
  }
};
// Word Break II
class Solution {  
 public:
  void DFS(const string &s, vector<vector<int>> &dp, int i,
           string words, vector<string> &ret) {
    if (i == dp.size()) {
      ret.push_back(words);
      return;
    }
    for (int j : dp[i]) {
      auto word = s.substr(i, j - i);
      DFS(s, dp, j, words + " " + word, ret);
    }
  }

  vector<string> wordBreak(
      string s, unordered_set<string> &wordDict) {
    const int n = s.size();
    if (n == 0) {
      return {};
    }
    // dp[i]: a list of available indics [i, j).
    vector<vector<int>> dp(n);
    for (int i = n - 1; i >= 0; --i) {
      for (int j = i + 1; j <= n; ++j) {
        auto word = s.substr(i, j - i);
        if (wordDict.count(word) > 0 &&
            (j == n || !dp[j].empty())) {
          dp[i].push_back(j);
        }
      }
    }
    // DFS.
    vector<string> ret;
    for (int j : dp[0]) {
      DFS(s, dp, j, s.substr(0, j), ret);
    }
    return ret;
  }
};