来源：编程网事
大家好，我就是那个在B站讲算法的「华南溜达虎」。
今天看到一位本科双非的同学面试华为车bu，走完了所有流程，目前在等待开奖，担心华为会卡第一学历，于是发了个求助帖。
有些同学说海思部门一定卡，其他部门不确定。还有同学表示能走完所有流程进备选池被捞的概率只有20%，大概率会卡。还有同学说od都卡他本科学历了，更别说正式员工了。看起来进池子被捞起来依旧是个小概率事件，所以大家还是要多做几手准备。
言归正传，今天我们来分享一道华为面试题「单词拆分」。
给你一个字符串 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];
}
};
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]
特别声明：以上内容仅代表作者本人的观点或立场，不代表新浪财经头条的观点或立场。如因作品内容、版权或其他问题需要与新浪财经头条联系的，请于上述内容发布后的30天内进行。
