暴力回溯
回溯過程就是一個決策樹模型，從所有選擇中找到合適的繼續，否則回到上一級繼續。
該方法思路簡單，時間復雜度過高，大概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];
}
)
