代码随想录算法训练营第46天 |139.单词拆分

TFTree 发布于 2023-03-08 686 次阅读


AI 摘要

本篇文章介绍了 Leetcode 中第 139 题“单词拆分”的解法。本文首先讲解了该题使用的动态规划思路,包括 dp 数组的定义、递推公式、初始化方式和遍历顺序。然后,文章展示了作者的 AC 代码及标准答案,同时分析了该算法的时间复杂度和空间复杂度。如果你对动态规划算法感兴趣,不妨阅读本文了解更多。

139. 单词拆分 - 力扣(Leetcode)

思路:

  • 使用动态规划

    1. 确定dp数组以及下标的含义

      • dp[j]的定义为:单词库中的单词可以构成j长度的给定字符串
    2. 确定递推公式

      // 状态转移方程
      // 考虑这样的情况,如果dp[j]为true且j到i的那段字符串存在于单词库中,则dp[i]为true
      if(wordSet.find(word) != wordSet.end() && dp[j] == true) {
          dp[i] = true;
      }
    3. dp数组如何初始化

      vector<bool> dp(s.size() + 1, false);
      dp[0] = true;
    4. 确定遍历顺序

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

我的AC代码(复刻)

// 时间复杂度:O(n^3),因为substr返回子串的副本是O(n)的复杂度(这里的n是substring的长度)
// 空间复杂度:O(n)
class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        unordered_set<string> wordSet(wordDict.begin(), wordDict.end());
        vector<bool> dp(s.size() + 1, false);
        dp[0] = true;
        for(int i = 1; i <= s.size(); ++i) {
            for(int j = 0; j < i; ++j) {
                string word = s.substr(j, i - j);
                if(wordSet.find(word) != wordSet.end() && dp[j] == true) {
                    dp[i] = true;
                }
            }
        }
        return dp[s.size()];
    }
};

标准答案

// 时间复杂度:O(n^3),因为substr返回子串的副本是O(n)的复杂度(这里的n是substring的长度)
// 空间复杂度:O(n)
class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        unordered_set<string> wordSet(wordDict.begin(), wordDict.end());
        vector<bool> dp(s.size() + 1, false);
        dp[0] = true;
        for (int i = 1; i <= s.size(); i++) {   // 遍历背包
            for (int j = 0; j < i; j++) {       // 遍历物品
                string word = s.substr(j, i - j); //substr(起始位置,截取的个数)
                if (wordSet.find(word) != wordSet.end() && dp[j]) {
                    dp[i] = true;
                }
            }
        }
        return dp[s.size()];
    }
};