判断字符串是否可以由字典中的字符串组成
发布时间
阅读量：
阅读量
在字节跳动的面试中遇到一道题目：对于给定的字符串s和词典dict，请判断是否能将该字符串分解为词典中词汇的组合。具体而言，则采用动态规划策略解决此问题。例如：当s = “I love bytedance”，而 dict = {“I”, “love”, “bytedance”}时
c++代码
bool wordBreak(string s, unordered_set<string> &dict) {
int n = s.size();
vector<bool> dp(n+1, false);
dp[0] = true;
for(int i= 0; i < n; ++i){
for(int j = i; dp[i]&&j<n; ++j){
if(dict.find(s.substr(i, j - i+1)) != dict.end())
dp[j+1] = true;
}
}
return dp[n];
}
代码解读全部评论 (0)
还没有任何评论哟~