备案网站查询租房信息网站建设

备案网站查询,租房信息网站建设,人成免费入口2022,河北邯郸网站建设公司给定字符串 s 和字符串字典 wordDict#xff0c;判断 s 是否可以被拆分为一个或多个字典中的单词。特点#xff1a;字典单词 可以重复使用不要求使用所有字典单词方法一#xff1a;暴力 DFS#xff08;递归#xff09;思路从字符串开头开始#xff1a;枚举前缀如果前缀在…给定字符串s和字符串字典wordDict判断s是否可以被拆分为一个或多个字典中的单词。特点字典单词可以重复使用不要求使用所有字典单词方法一暴力 DFS递归思路从字符串开头开始枚举前缀如果前缀在字典中递归判断剩余部分例如applepenapple apple | penapple pen | apple如果能拆分到最后返回true。C 代码#include stdbool.h #include string.h bool inDict(char* s, int start, int len, char** wordDict, int wordDictSize) { for(int i 0; i wordDictSize; i) { if(strlen(wordDict[i]) len strncmp(s start, wordDict[i], len) 0) return true; } return false; } bool dfs(char* s, int start, int len, char** wordDict, int wordDictSize) { if(start len) return true; for(int i start 1; i len; i) { if(inDict(s, start, i - start, wordDict, wordDictSize) dfs(s, i, len, wordDict, wordDictSize)) return true; } return false; } bool wordBreak(char* s, char** wordDict, int wordDictSize) { return dfs(s, 0, strlen(s), wordDict, wordDictSize); }复杂度时间复杂度O(2^n) 空间复杂度O(n)因为大量重复计算容易超时。方法二DFS 记忆化搜索剪枝思路暴力 DFS 的问题重复计算同一个子问题例如applepenapple apple我们可以记录start 位置是否可以拆分用数组memo[]记录状态0 未计算 1 可以拆分 -1 不可以拆分C 代码#include stdbool.h #include string.h int memo[305]; bool inDict(char* s, int start, int len, char** wordDict, int wordDictSize) { for(int i 0; i wordDictSize; i) { if(strlen(wordDict[i]) len strncmp(s start, wordDict[i], len) 0) return true; } return false; } bool dfs(char* s, int start, int len, char** wordDict, int wordDictSize) { if(start len) return true; if(memo[start] ! 0) return memo[start] 1; for(int i start 1; i len; i) { if(inDict(s, start, i - start, wordDict, wordDictSize) dfs(s, i, len, wordDict, wordDictSize)) { memo[start] 1; return true; } } memo[start] -1; return false; } bool wordBreak(char* s, char** wordDict, int wordDictSize) { memset(memo, 0, sizeof(memo)); return dfs(s, 0, strlen(s), wordDict, wordDictSize); }复杂度时间复杂度O(n² * m) 空间复杂度O(n)方法三动态规划最经典这是LeetCode 官方最推荐方法。DP 思路定义dp[i] 表示 s[0..i-1] 是否可以拆分初始化dp[0] true状态转移dp[i] dp[j] s[j..i-1] 在字典中其中0 ≤ j iC 代码#include stdbool.h #include string.h bool inDict(char* s, int start, int len, char** wordDict, int wordDictSize) { for(int i 0; i wordDictSize; i) { if(strlen(wordDict[i]) len strncmp(s start, wordDict[i], len) 0) return true; } return false; } bool wordBreak(char* s, char** wordDict, int wordDictSize) { int n strlen(s); bool dp[n 1]; memset(dp, false, sizeof(dp)); dp[0] true; for(int i 1; i n; i) { for(int j 0; j i; j) { if(dp[j] inDict(s, j, i - j, wordDict, wordDictSize)) { dp[i] true; break; } } } return dp[n]; }复杂度时间复杂度O(n² * m) 空间复杂度O(n)方法四DP 哈希优化最优解优化点1️⃣ 使用HashSet加速查找2️⃣ 限制单词最大长度题目给出wordDict[i].length ≤ 20因此j i - 20减少无效判断。优化版 C 代码#include stdbool.h #include string.h bool inDict(char* s, int start, int len, char** wordDict, int wordDictSize) { for(int i 0; i wordDictSize; i) { if(strlen(wordDict[i]) len strncmp(s start, wordDict[i], len) 0) return true; } return false; } bool wordBreak(char* s, char** wordDict, int wordDictSize) { int n strlen(s); bool dp[n 1]; memset(dp, false, sizeof(dp)); dp[0] true; for(int i 1; i n; i) { for(int j i - 20; j i; j) { if(j 0 dp[j] inDict(s, j, i - j, wordDict, wordDictSize)) { dp[i] true; break; } } } return dp[n]; }DP过程图解示例s leetcode dict [leet,code]索引0 1 2 3 4 5 6 7 8 l e e t c o d eDP数组T F F F T F F F T解释dp[4] true (leet) dp[8] true (code)面试总结最推荐回答顺序1 暴力DFS 2 DFS 记忆化 3 动态规划重点 4 DP优化面试官最希望听到DP 状态定义 状态转移