LeetCode-Solutions-in-Cpp17

Solutions to high-frequency interview questions of LeetCode in C++17, taking into account both efficiency and comprehensibility.

---

Project maintained by downdemo Hosted on GitHub Pages — Theme by mattgraham

• 动态规划，dp[i] 表示 s 的前 i 个字符能拆分为字典中的单词

dp[0] = true;
dp[i] = dp[j] 且 s[j]...s[i - 1] 在字典中

["leet", "code"]
leetcode

记 x 在字典中为 f(x)
dp[0] = true;
dp[1] = dp[0] && f("l") = false
dp[2] = false
  dp[0] && f("le") = false
  dp[1] && f("e") = false
dp[3] = false
  dp[0] && f("lee") = false
  dp[1] && f("ee") = false
  dp[2] && f("e") = false
dp[4] = true
  dp[0] && f("leet") =true
dp[5] = false
  dp[0] && f("leetc") = false
  dp[1] && f("eetc") = false
  dp[2] && f("etc") = false
  dp[3] && f("tc") = false
  dp[4] && f("c") = false
dp[6] = false
dp[7] = false
dp[8] = true
  dp[4] && f("code") = true

结束，返回dp[8]

• 解法如下

class Solution {
 public:
  bool wordBreak(string s, vector<string>& wordDict) {
    unordered_set<string> wordSet{begin(wordDict), end(wordDict)};
    vector<bool> dp(size(s) + 1);
    dp[0] = true;
    for (int i = 1; i < size(dp); ++i) {
      for (int j = 0; j < i; ++j) {
        if (dp[j] && wordSet.count(s.substr(j, i - j))) {
          dp[i] = true;
          break;
        }
      }
    }
    return dp.back();
  }
};