【Leetcode】【Medium】Word Break

时间:2024-04-29 09:55:09

Given a string s and a dictionary of words dict, determine if s can be segmented into a space-separated sequence of one or more dictionary words.

For example, given
s = "leetcode",
dict = ["leet", "code"].

Return true because "leetcode" can be segmented as "leet code".

解题思路:

可以使用动态规划的思想,如果S[0~i]在dict中是可分的,那么只需考察S[i+1~n]在dict中可分即可;

具体步骤:

新建一个和S字符串长度相等的数组,用来记录S从0~i的各个子串是否被dict可分;

从S串的第一个字符开始,逐渐增加字符,考察是否可分:

对于待考察的S[0~i]字符串,如果S[0~j]已经在之前的考察中证实是可分的,那么只需判断S[j+1~i]是否可分;

代码:

 class Solution {
public:
bool wordBreak(string s, unordered_set<string>& wordDict) {
vector<bool> seg_flag(s.size(), false); for (int i = ; i < s.size(); ++i) {
if (wordDict.find(s.substr(, i+)) != wordDict.end()) {
seg_flag[i] = true;
continue;
} for (int j = i; j >= ; --j) {
if (seg_flag[j-] == true && (wordDict.find(s.substr(j, i - j + )) != wordDict.end())) {
seg_flag[i] = true;
break;
}
}
} return seg_flag[s.size() - ];
}
};