专栏：50多种数据结构彻底征服

专栏：50多种经典图论算法全部掌握

一员工在公司工作了8年被裁，赔偿了22万，刚找到工作，结果前公司就想通过涨薪的方式让他继续回来上班，并且把赔偿金还回去。回去上班可以，为什么要还赔偿金，万一还了之后不到一个月开除，岂不是啥赔偿都没了。

网友评论：

--------------下面是今天的算法题--------------

来看下今天的算法题，这题是LeetCode的第139：单词拆分。

问题描述

来源：LeetCode第139题

难度：中等

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

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

示例1：

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

示例2：

输入: 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 中的所有字符串 互不相同

问题分析

这题判断能否用字典中的字符串拼接成字符串 s ，实际上就是把字符串 s 拆分成一些子串，并且判断这些子串是否都存在字典wordDict中。这题解决方式比较多，有动态规划，还有BFS和DFS，我们先来看动态规划怎么解决。

定义dp[i]表示字符串的前 i 个字符经过拆分是否都存在于字典wordDict中。如果求dp[i]，需要往前截取 k 个字符，判断子串[i-k+1，i]是否存在于字典wordDict中，并且前面子串[0，i-k]拆分的子串也是否都存在于wordDict中，如果都存在，说明可以拆分

JAVA：

public boolean wordBreak(String s, List  wordDict)  {
    int len = s.length();
    boolean[] dp = new boolean[len + 1];
    dp[0] = true;// 空字符串，不需要字典中的字符串。
    for (int i = 1; i <= len; i++) {
        for (int j = 0; j < i; j++) {
            // 把字符串分割为s[0,j-1]和s[j,i]两部分，
            // 这两部分必须都存在于字典中dp[i]才会返回true。
            dp[i] = dp[j] && wordDict.contains(s.substring(j, i));
            if (dp[i])// 只要有一种方式能够拆分成功，后面就不要尝试拆分了。
                break;
        }
    }
    return dp[len];
}

C++：

public:
    bool wordBreak(string s, vector

  &wordDict) {         size_t len = s.size();         vector

  dp(len + 1, false);         unordered_set

  wordSet(wordDict.begin(), wordDict.end());         dp[0] = true;// 空字符串，不需要字典中的字符串。         for (int i = 1; i <= len; i++) {             for (int j = 0; j < i; j++) {                 // 把字符串分割为s[0,j-1]和s[j,i]两部分，                 // 这两部分必须都存在于字典中dp[i]才会返回true。                 if (dp[j] && wordSet.find(s.substr(j, i - j)) != wordSet.end()) {                     dp[i] = true;// 只要有一种方式能够拆分成功，后面就不要尝试拆分了。                     break;                 }             }         }         return dp[len];     }

Python：

def wordBreak(self, s: str, wordDict: List[str]) -> bool:
    len_s = len(s)
    dp = [False] * (len_s + 1)
    dp[0] = True  # 空字符串，不需要字典中的字符串。
    for i in range(1, len_s + 1):
        for j in range(i):
            # 把字符串分割为s[0,j-1]和s[j,i]两部分，
            # 这两部分必须都存在于字典中dp[i]才会返回true。
            if dp[j] and s[j:i] in wordDict:
                dp[i] = True
                # 只要有一种方式能够拆分成功，后面就不要尝试拆分了。
                break
    return dp[len_s]

笔者简介

博哥，真名：王一博，毕业十多年， 作者，专注于 数据结构和算法 的讲解，在全球30多个算法网站中累计做题2000多道，在公众号中写算法题解800多题，对算法题有自己独特的解题思路和解题技巧，喜欢的可以给个关注，也可以 下载我整理的1000多页的PDF算法文档 。