大家好，我就是那个在B站讲算法的「华南溜达虎」。
今天看到一位本科双非的同学面试华为车bu，走完了所有流程，目前在等待开奖，担心华为会卡第一学历，于是发了个求助帖。
有些同学说海思部门一定卡，其他部门不确定。还有同学表示能走完所有流程进备选池被捞的概率只有20%，大概率会卡。还有同学说od都卡他本科学历了，更别说正式员工了。看起来进池子被捞起来依旧是个小概率事件，所以大家还是要多做几手准备。
25届秋招已经开始了，我组织了一个秋招群，大家可以交流学习心得、面试经验，分享工作机会，有啥问题也可以在群里咨询。在群里我整理了一百多家已经启动秋招企业的文档，以及投递入口，每天都会更新，大家只要按照这个文档海投就可以了。
大家互帮互助相信一定可以拿下秋招！计算机相关专业的同学可以 点击底部的「阅读原文」 加群。
言归正传，今天我们来分享一道华为面试题「单词拆分」。
题目描述
给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。
注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。
举个例子：
输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true
解释: 返回 true 因为 "leetcode" 可以由 "leet" 和 "code" 拼接成。
思路解析
本题是一道经典的动态规划问题，要找到解决动态规划问题的两个突破点：推导出状态转移公式和边界条件处理。
首先定义dp[i]为字符串s的[0, i)区间是否可以利用字典中出现的单词拼接。dp[i] == true代表可以。
对于s = "leetcode", wordDict = ["hello", "leet", "code"]的推导树如下:
推导的核心思想就是：
在遍历 s的过程中如果满足wordDict中的单词word和字符串s的区间[i, i + len(word))组成的子串相同且dp[i] == true，就更新dp[i+len(word)] = dp[i]。
所以状态转移公式 就是dp[i+len(word)] = dp[i]。定义边界条件 dp[0] = true。
对于上面的例子dp[8] = dp[4] = dp[0] = true。
下面我们给出c++和python的两种代码实现。
C++代码
class Solution {
public:
bool wordBreak(string s, vector<string>& wordDict) {
int s_len = s.length();
//定义dp数组，dp[i]表示s的前i个字符能否被wordDict中的单词完全拆分
vector<bool> dp(s_len + 1, false);
//初始条件：空字符串可以被拆分
dp[0] = true;
for (int i = 0; i < s_len; ++i) {
for (auto& word:wordDict) {
int word_len = word.length();
//如果以s[i]开头的长度为word_len的子串与word相等，则更新dp[i + word_len]
if (dp[i] && (i + word_len <= s_len) && s.substr(i, word_len) == word) {
//状态转移公式
dp[i + word_len] = dp[i];
}
}
}
return dp[s_len];
}
};
python代码
class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
s_len = len(s)
# 定义dp数组，dp[i]表示s的前i个字符能否被wordDict中的单词完全拆分
dp = [False] * (s_len + 1)
# 初始条件：空字符串可以被拆分
dp[0] = True
for i in range(s_len):
if dp[i]:
for word in wordDict:
word_len = len(word)
# 如果以s[i]开头的长度为word_len的子串与word相等，则更新dp[i + word_len]
if i + word_len <= s_len and s[i:i+word_len] == word:
# 状态转移公式
dp[i + word_len] = True
# 返回dp数组的最后一个值，表示整个字符串s是否可以被拆分
return dp[s_len]
复杂度分析
时间复杂度： O(mn)，其中m为s的长度，n为wordDict的长度。
空间复杂度： O(m)，其中m为s的长度。
号外
经常使用leetcode会员的同学可以使用我的优惠通道啦！
https://leetcode.cn/premium/?promoChannel=ldtiger ，年度会员有效期比官网多俩月，季度会员有效期比官网多两个星期，还有专属福利，需要的读者朋友可以找我了解。
今天的分享就到这里，希望大家能有所收获！
