leetcode-139. 单词拆分-C

暴力回溯

回溯过程就是一个决策树模型，从所有选择中找到合适的继续，否则回到上一级继续。

该方法思路简单，时间复杂度过高，大概1/4的用例超时。

bool backtrack(char *s, int cur, char** wordDict, int wordDictSize) {// 基线条件if(cur == strlen(s)) {return true;}bool res = false;for(int i=0; i<wordDictSize; i++) {// 选择判断char *tmp = strstr(s+cur, wordDict[i]);if(tmp == s+cur) {// 下一级res |= backtrack(s, cur+strlen(wordDict[i]), wordDict, wordDictSize);}}// 所有选择不对时回退return res;
}
bool wordBreak(char* s, char** wordDict, int wordDictSize) {return backtrack(s, 0, wordDict, wordDictSize);
}

动态规划

• 定义dp: dp[i]表示s中0到i-1是否可以由单词列表中单词组成
• 转移方程：dp[i] = dp[i-len(word)] && (s[i-len(word) ~ i-1] == word)

遍历顺序保证dp[i-len(word)]在进行dp[i]判断时已经是有效的

bool wordBreak(char* s, char** wordDict, int wordDictSize) {int n = strlen(s);bool dp[n+1];memset(dp, 0, sizeof(dp));dp[0] = true;for(int i=1; i<=n; i++) {for(int j=0; j<wordDictSize; j++) {int tmp = strlen(wordDict[j]);// 转移方程if(i >= tmp && dp[i-tmp] && strstr(s+i-tmp, wordDict[j]) == s+i-tmp) {dp[i] = true;break;}}}return dp[n];
}