当前位置：首页 > article >正文

LeetCode 算法：单词拆分 c++

article 2024/11/14 3:12:44

原题链接🔗：单词拆分
难度：中等⭐️⭐️

题目

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。

注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。

示例 1：

输入: s = “leetcode”, wordDict = [“leet”, “code”]
输出: true
解释: 返回 true 因为 “leetcode” 可以由 “leet” 和 “code” 拼接成。
示例 2：

输入: s = “applepenapple”, wordDict = [“apple”, “pen”]
输出: true
解释: 返回 true 因为 “applepenapple” 可以由 “apple” “pen” “apple” 拼接成。
注意，你可以重复使用字典中的单词。
示例 3：

输入: s = “catsandog”, wordDict = [“cats”, “dog”, “sand”, “and”, “cat”]
输出: false

提示：

1 <= s.length <= 300
1 <= wordDict.length <= 1000
1 <= wordDict[i].length <= 20
s 和 wordDict[i] 仅由小写英文字母组成
wordDict 中的所有字符串互不相同

动态规划

动态规划（Dynamic
Programming，简称DP）是一种在数学、管理科学、计算机科学和经济学中使用的，通过把原问题分解为相对简单的子问题的方式来求解复杂问题的方法。动态规划常常用于优化问题，特别是那些具有重叠子问题和最优子结构性质的问题。

动态规划的一般步骤包括：

问题定义：明确要解决的问题，并确定状态和决策。
递推关系（状态转移方程）：找出问题的递推公式，即状态转移方程，它描述了问题的不同阶段之间的关系。
边界条件：确定初始状态或基本情况，为递推提供起点。
计算顺序：确定各状态按照什么顺序进行计算，以保证在计算当前状态时，所需要的子状态已被计算。
计算与存储：按照确定的顺序，逐个计算每个状态的值，并将其存储下来，以便在需要时使用。
构造解：根据计算得到的状态值，构造问题的解。

动态规划通常用于解决以下类型的问题：

背包问题：包括0-1背包问题、完全背包问题和多重背包问题等。
最长递增子序列：找出序列中最长的递增子序列。
最短路径问题：如Dijkstra算法和Floyd算法。
矩阵链乘问题：计算矩阵连乘的最优顺序。
硬币找零问题：最少硬币找零问题。
编辑距离问题：计算两个字符串之间的编辑距离。

动态规划的关键点在于识别问题的最优子结构和递归性质，以及如何将问题分解为更小的子问题。通过存储子问题的解，可以避免重复计算，从而提高算法的效率。

题解

解题思路：

LeetCode 上的 “单词拆分” 问题是一个经典的动态规划问题。题目要求是给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，判定 s 是否可以被空格拆分成一个或多个在字典中出现的单词。例如：

输入: s = “leetcode”, wordDict = [“leet”, “code”] 输出: true

解释: 返回 true 因为 “leetcode” 可以被拆分成 “leet code”。

解题思路：动态规划

定义状态：dp[i] 表示字符串 s 从索引 0 到索引 i（包含索引 i）的部分是否可以完全由 wordDict 中的单词组成。

状态转移方程：对于每个 i，我们需要检查所有可能的 j（j < i），看 s[j+1…i] 是否是 wordDict 中的一个单词。如果是，并且 dp[j] 为 true，那么 dp[i] 就可以设置为 true。

初始化：dp[0] = true，因为空字符串总是可以被拆分。

计算顺序：按照字符串 s 的索引从小到大的顺序计算 dp 数组。

结果：dp[len(s)-1] 就是整个字符串 s 是否可以被拆分。

c++ demo：

#include <iostream>
#include <string>
#include <vector>
#include <unordered_set>

class Solution {
public:
    bool wordBreak(std::string s, std::vector<std::string>& wordDict) {
        std::unordered_set<std::string> words(wordDict.begin(), wordDict.end());
        std::vector<bool> dp(s.length() + 1, false);
        dp[0] = true;

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

int main() {
    Solution solution;
    std::string s = "leetcode";
    std::vector<std::string> wordDict = { "leet", "code" };
    bool result = solution.wordBreak(s, wordDict);
    std::cout << (result ? "true" : "false") << std::endl;
    return 0;
}