力扣139、单词拆分


题目

给你一个字符串 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);
}


文章作者: Axieyun
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 Axieyun !
评论
评论
  目录