许昌网站建设汉狮套餐,为什么网站打不开首页,wordpress首页显示文章列表,wordpress 做博客题目 时间复杂度为O(n^2)#xff0c;其中n为字符串s的长度。这是因为我们需要遍历字符串s的每个位置#xff0c;对于每个位置i#xff0c;又需要从0到i-1的位置进行遍历#xff0c;因此总的时间复杂度为O(n^2)。
空间复杂度为O(n)#xff0c;其中n为字符串s的长度。这是因…题目 时间复杂度为O(n^2)其中n为字符串s的长度。这是因为我们需要遍历字符串s的每个位置对于每个位置i又需要从0到i-1的位置进行遍历因此总的时间复杂度为O(n^2)。
空间复杂度为O(n)其中n为字符串s的长度。这是因为我们使用了一个大小为n1的dp数组来保存中间结果以及一个unordered_set来存储wordDict中的单词。因此总的空间复杂度为O(n)。 中等
相关标签 给你一个字符串 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 3001 wordDict.length 10001 wordDict[i].length 20s 和 wordDict[i] 仅由小写英文字母组成wordDict 中的所有字符串 互不相同
思路和解题方法 首先我们将wordDict中的单词存储在一个unordered_set中这样可以以O(1)的时间复杂度进行单词的查找。接下来我们定义一个dp数组dp[i]表示字符串s的前i个字符能否被拆分成wordDict中的单词。我们初始化dp[0]为true表示空字符串可以被拆分。然后我们从字符串s的第一个字符开始遍历到最后一个字符。对于每个位置i我们再从0到i-1的位置遍历记为位置j。我们要判断以位置j为分割点左边子串能否被拆分并且右边子串s[j:i-1]在wordDict中存在。具体地我们检查dp[j]是否为true即前j个字符能否被拆分成wordDict中的单词。如果dp[j]为true并且子串s[j:i-1]在wordDict中存在即wordDictSet.find(s.substr(j, i - j)) ! wordDictSet.end()那么我们可以更新dp[i]为true。在内层循环中我们不断更新dp[i]的值直到找到一个满足条件的分割点j或者遍历完所有可能的分割点。最终返回dp[s.size()]即整个字符串s是否可以被拆分成wordDict中的单词的结果。 复杂度 时间复杂度: O(n^2) 时间复杂度为O(n^2)其中n为字符串s的长度。这是因为我们需要遍历字符串s的每个位置对于每个位置i又需要从0到i-1的位置进行遍历因此总的时间复杂度为O(n^2)。 空间复杂度 O(n) 空间复杂度为O(n)其中n为字符串s的长度。这是因为我们使用了一个大小为n1的dp数组来保存中间结果以及一个unordered_set来存储wordDict中的单词。因此总的空间复杂度为O(n)。 c 代码
class Solution {
public:bool wordBreak(string s, vectorstring wordDict) {// 将wordDict转化为unordered_set以便快速查找auto wordDictSet unordered_setstring();for (auto word : wordDict) {wordDictSet.insert(word);}// 定义dp数组dp[i]表示s的前i个字符能否被拆分成wordDict中的单词auto dp vectorbool(s.size() 1);dp[0] true; // 初始化dp[0]为true表示空字符串可以被拆分// 遍历字符串s的每个位置判断从0到当前位置的子串能否被拆分for (int i 1; i s.size(); i) {for (int j 0; j i; j) {// 如果dp[j]为true且s[j:i-1]在wordDict中则更新dp[i]为trueif (dp[j] wordDictSet.find(s.substr(j, i - j)) ! wordDictSet.end()) {dp[i] true;break;}}}// 返回dp[s.size()]即整个字符串s是否可以被拆分成wordDict中的单词return dp[s.size()];}
};Java代码
class Solution {public boolean wordBreak(String s, ListString wordDict) {// 使用HashSet来存储单词以提高查找速度HashSetString set new HashSet(wordDict);// valid数组记录s的前i个字符是否可以被拆分成单词boolean[] valid new boolean[s.length() 1];valid[0] true; // 空字符串可以被拆分for (int i 1; i s.length(); i) {for (int j 0; j i !valid[i]; j) {// 如果在j和i之间存在一个分割点使得前半部分和后半部分都可以被拆分成单词// 则将valid[i]设为trueif (set.contains(s.substring(j, i)) valid[j]) {valid[i] true;}}}return valid[s.length()];}
}使用了动态规划的思想通过遍历字符串s的每个位置判断是否存在一个分割点使得前半部分和后半部分都可以被拆分成单词。时间复杂度为O(n^2)空间复杂度为O(n)。 class Solution {public boolean wordBreak(String s, ListString wordDict) {// dp数组记录s的前i个字符是否可以被拆分成单词boolean[] dp new boolean[s.length() 1];dp[0] true; // 空字符串可以被拆分for (int i 1; i s.length(); i) {for (String word : wordDict) {int len word.length();// 如果i的前len个字符可以被拆分成单词并且最后一个单词和word相等则将dp[i]设为trueif (i len dp[i - len] word.equals(s.substring(i - len, i))) {dp[i] true;break;}}}return dp[s.length()];}
}使用了动态规划的思想通过遍历字符串s的每个位置判断是否存在一个分割点使得前半部分和后半部分都可以被拆分成单词。时间复杂度为O(n^2)空间复杂度为O(n)。 class Solution {private SetString set;private int[] memo;public boolean wordBreak(String s, ListString wordDict) {// memo数组用于记录从startIndex开始的子串是否可以被拆分成单词memo new int[s.length()];// 使用HashSet来存储单词以提高查找速度set new HashSet(wordDict);return backtracking(s, 0);}public boolean backtracking(String s, int startIndex) {if (startIndex s.length()) {return true; // 已经遍历到字符串末尾返回true}if (memo[startIndex] -1) {return false; // 从startIndex开始的子串已经被标记为不能匹配直接返回false}for (int i startIndex; i s.length(); i) {String sub s.substring(startIndex, i 1);if (!set.contains(sub)) {continue; // 如果拆分出来的单词不在wordDict中则继续尝试下一个分割点}boolean res backtracking(s, i 1);if (res) return true; // 如果后半部分可以被拆分则返回true}memo[startIndex] -1; // 从startIndex开始的子串无法匹配标记为-1return false;}
}使用了回溯法和记忆化的思想。通过递归地尝试每个分割点判断前半部分是否可以被拆分成单词如果可以则继续递归判断后半部分。为了避免重复计算使用memo数组记录已经判断过的子串。时间复杂度取决于所有可能的分割方式最坏情况下为O(2^n)空间复杂度为O(n)。 觉得有用的话可以点点赞支持一下。
如果愿意的话关注一下。会对你有更多的帮助。 每天都会不定时更新哦 人 。
