【记忆回溯】【深度搜索】【动态规划】【字符串】【力扣】单词拆分

目录

题目描述

解题思路

解答（c语言）

题目描述

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。

注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。

示例 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

解题思路

解题思路：深度遍历的思想

从字符串的起始位置开始匹配字典中的单词，如果能匹配到，则继续从字符串中该单词后面继续匹配字典中的单词，直到完全匹配。

• 比如s = "catsandog"，wordDict = {"cats","dog","sand","and","cat"}
• index = 0时，对"catsandog"进行前缀匹配，可以匹配到"cats"，也可以匹配到"cat"等，则需要记忆回溯，也就是深度遍历，先匹配到"cats"处理，然后更新index = 4
• index = 4时，对"andog"进行前缀匹配，匹配到"and"，然后更新index = 7
• index = 7时，对"og"进行前缀匹配，没有一个能匹配，然后返回到index = 4时，寻找能否有匹配的单词，已经匹配过的不再匹配，比如"and"
  • 如果index = 4时没有可匹配的，返回index = 0时的前缀匹配，寻找能否有匹配的单词
  • 如果index = 4时有可匹配的，则继续向下匹配，像刚才那样
• 就这样，来来回回寻找（深度遍历），直到index = strlen(s)，说明可以s能被wordDict拼接。如果index从0到1，到2，到strlen(s) - 1对字典所有匹配都尝试完了，仍然没有则说明不能被拼接

注意点：已经匹配过的不再匹配，提交后才发现，否则会超时，因为会有很多重复判断

解答（c语言）

#include <ctype.h>
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>int isMatch = 0;  // 标记能否被分割int Forward(int index, char* s, size_t sLen, char **wordDict, int wordDictSize, int *isHasJudge)
{// 一旦有拼接成功的方案，则不再找寻其它方案if (isMatch == 1) {return 1;}// 恰好拼接成功if (index == sLen) {isMatch = 1;return 1;}// 无法拼接成功if (index > sLen) {return -1;}// 判断过的不再判断if (isHasJudge[index] == 1) {return -1;}// 遍历全部单词判断for (int j = 0; j < wordDictSize; j++) {size_t len = strlen(wordDict[j]);if (strncmp(s + index, wordDict[j], len) == 0) {int ret = Forward(index + len, s, sLen, wordDict, wordDictSize, isHasJudge);if (ret == 1) {return 1;}}}// 已判断过的做好标记isHasJudge[index] = 1;// 如果没有一个单词能匹配，则返回负数return -1;
}bool wordBreak(char* s, char **wordDict, int wordDictSize) 
{// 每个用例会更改全局变量，需要重新初始化isMatch = 0;  size_t sLen = strlen(s);// 记录每个下标（0,1,2，..., sLen-1）是否已经和所有子串匹配过int isHasJudge[sLen]; memset(isHasJudge, 0, sizeof(isHasJudge));// 深度遍历寻找所有方案Forward(0, s, sLen, wordDict, wordDictSize, isHasJudge);return isMatch == 1;
}int main() 
{int select = 3;if (select == 1) {char *s = "catsandog";char *wordDict[] = {"cats","dog","sand","and","cat"};wordBreak(s, wordDict, 5);} else if  (select == 2) {char *s = "applepenapple";char *wordDict[] = {"apple","pen"};wordBreak(s, wordDict, 2);} else if (select == 3) {char *s = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab";char *wordDict[] = {"a","aa","aaa","aaaa","aaaaa","aaaaaa","aaaaaaa","aaaaaaaa","aaaaaaaaa","aaaaaaaaaa"};wordBreak(s, wordDict, 10);}return 0;
}

end