题目
给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。
注意:不要求字典中出现的单词全部都使用,并且字典中的单词可以重复使用。
示例 1:
输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true
解释: 返回 true 因为 "leetcode" 可以由 "leet" 和 "code" 拼接成。
示例 2:
输入: s = "applepenapple", wordDict = ["apple", "pen"]
输出: true
解释: 返回 true 因为 "applepenapple" 可以由 "apple" "pen" "apple" 拼接成。
注意,你可以重复使用字典中的单词。
示例 3:
输入: 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 中的所有字符串 互不相同
思路
- dfs
- 搜索字典,判断字典中的字符串是否是文本串s的前缀子串
- 是的话,继续搜索,判断文本串后面的子串是否能被字典的串拼接(重复上面步骤)
- dfs边界:
- 1、搜索到文本串s的结尾,返回真
- 2、记忆化搜索,剪枝,缓冲搜索状态
题解
//判断单词是否是文本串s的前缀串
bool isWord(const char *s, const char *word, const int len_w) {
if (len_w > strlen(s)) return false;
for (int i = 0; *(word + i); ++i) {
if ( (*(word + i)) ^ (*(s + i)) ) return false;
}
return true;
}
short record[301];
bool dfs(const char *s, const int sstart, const char **wordDict, const int wordDictSize) {
if ( *(s + sstart) == '\0') return true; //递归边界
if( *(record + sstart) != -1) { //剪枝,成功或者失败过
return *(record + sstart);
}
for(int word_idx = 0; word_idx < wordDictSize; ++word_idx) {
int len_w = strlen( *(wordDict + word_idx));
if(isWord(s + sstart, *(wordDict + word_idx), len_w)) { //该字符串是s子串
if(dfs(s, sstart + len_w, wordDict, wordDictSize)) { //它后面的串也是s的子串
*(record + sstart) = 1; // 成功的标志
return true;
}
}
}
*(record + sstart) = 0; //失败也是一种标志
return false;
}
bool wordBreak(char * s, char ** wordDict, int wordDictSize){
memset(record, -1, sizeof(short) * 301); // 初始化,没讲过世面
return dfs(s, 0, wordDict, wordDictSize);
}