最近在网上看到一个新闻，一位游戏大厂员工的女友，发文炫耀自己未婚夫2024年薪突破300万，前不久过生日直接给她转了4万零花钱，还在广州买了一套大平层，本打算在今年十一准备结婚的。结果被同一家公司员工发现，并举报，最后被裁。
实际上这种"坑夫式炫富"并非个例。2022年中金交易员妻子晒出的8.25万月薪单，直接引发金融圈薪酬整顿风暴，全行业人均薪资缩水20%。虽然说互联网公司薪资都是保密的，有的甚至还会签订保密协议，薪资不能向外人透露，但也不至于被裁吧，我想应该还有其他原因。
--------------下面是今天的算法题--------------
来看下今天的算法题，这题是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中，如果都存在，说明可以拆分。
如下图所示，如果我们要判断字符串“catsan”是否可以正常拆分，我们先截取前 6 个字符，判断它们是否存在于字典中，如果不存在，就截取 5 个，4个……，如果存在，还需要判断剩下的字符是否可以正常拆分。
JAVA：
public boolean wordBreak(String s, List<String> wordDict) { int len = s.length(); boolean[] dp = newboolean[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<string> &wordDict) { size_t len = s.size(); vector<bool> dp(len + 1, false); unordered_set<std::string> 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]; }
