e展网网站的建设情况,做精美得ppt网站知乎,想学网站建设方向的研究生,网站建设需要客户提供什么题目描述 有重复字符串的排列组合。编写一种方法#xff0c;计算某字符串的所有排列组合。 示例1:
输入#xff1a;S “qqe” 输出#xff1a;[“eqq”,“qeq”,“qqe”]
示例2:
输入#xff1a;S “ab” 输出#xff1a;[“ab”, “ba”]
提示:
字符都是英文字母。…题目描述 有重复字符串的排列组合。编写一种方法计算某字符串的所有排列组合。 示例1:
输入S “qqe” 输出[“eqq”,“qeq”,“qqe”]
示例2:
输入S “ab” 输出[“ab”, “ba”]
提示:
字符都是英文字母。 字符串长度在[1, 9]之间。
解题思路与代码
这道题一看还是一道关于排列的问题。只要有关排列的问题我们都可以通过回溯法去解决。
方法一 回溯法 使用unordered_set数据结构进行去重 如果没有做过《程序员面试金典第6版》面试题 08.07. 无重复字符串的排列组合回溯算法全排列问题C 这道题的小伙伴先去做一下这道题。 这道题与上面链接的那道题非常像只不过这里字符串中的字符开始出现有重复的字符了。所以我们做这道题的时候就需要去重。我们直接用unordered_set这种数据结构去去一下重好了。代码与上道题的代码没什么区别这里给出这道题的代码
class Solution {
public:vectorstring permutation(string S) {unordered_setstring result;backtracking(S,result,0);vectorstring vec;for(auto a : result){vec.push_back(a);}return vec;}void backtracking(string S,unordered_setstring result,int begin){if(begin S.size()){result.insert(S);return;}for(int i begin;i S.size(); i){swap(S[i],S[begin]);backtracking(S,result,begin1);swap(S[i],S[begin]);}}
};复杂度分析
时间复杂度 这段代码的时间复杂度主要取决于两个部分backtracking 函数的执行次数以及将结果从 unordered_set 转移到 vector 的时间。 backtracking 函数的执行次数对于长度为 n 的字符串我们需要对每个字符进行排列组合这会产生 n! 个排列。在回溯算法中我们会遍历整个排列空间。因此backtracking 函数的执行次数为 O(n!)。 将结果从 unordered_set 转移到 vectorresult 中最多有 n! 个元素。遍历 result 并将其中的元素插入 vector 的时间复杂度为 O(n!)。 综合这两部分总的时间复杂度为 O(n!)。
空间复杂度 空间复杂度主要取决于三个方面递归调用栈的深度、结果存储在 unordered_set 中所占用的空间以及结果向量 vec 所占用的空间。 递归调用栈的深度在回溯算法中递归调用栈的深度等于字符串的长度 n。因此递归调用栈的空间复杂度为 O(n)。 结果存储在 unordered_set 中所占用的空间result 中最多有 n! 个元素每个元素是一个长度为 n 的字符串。因此结果存储在 unordered_set 中所占用的空间复杂度为 O(n * n!)。 结果向量 vec 所占用的空间vec 中有 n! 个元素每个元素是一个长度为 n 的字符串。因此结果向量所占用的空间复杂度为 O(n * n!)。 由于这三部分空间是算法使用的空间因此总的空间复杂度为这三者之和即 O(n) O(n * n!) O(n * n!) O(2 * n * n!) O(n * n!)。 所以这段代码的时间复杂度为 O(n!)空间复杂度为 O(n * n!)。
方法二 对代码一的方法进行优化。
在这道题里因为可能有重复的字符方法一是直接用unordered_set在结果处进行去重重复的答案不会被存进集合中,但这种方法不会减少递归的此时。那有没有一种方法可以在做交换的时候就进行剪枝操作而进行去重呢而去减少递归的次数呢
答案当然是有我们可以通过一个unordered_set去记住在当前的这一层循环里出现过哪些字符如果出现了重复的字符那我们就跳过这次交换直接进入下一次交换。这样也同样达到了去重的目的也减少了递归的次数。但是不好的一点是增加了内存的存储空间因为每一层递归都要创建一个unordered_set去存储出现过的字符。
具体代码如下
class Solution {
public:vectorstring permutation(string S) {vectorstring result;backtracking(S, result, 0);return result;}void backtracking(string S, vectorstring result, int begin) {if (begin S.size()) {result.push_back(S);return;}unordered_setchar used_chars; // 用于存储已经在当前位置出现过的字符for (int i begin; i S.size(); i) {if (used_chars.find(S[i]) ! used_chars.end()) {continue; // 如果当前字符已经在当前位置出现过则跳过这次交换}used_chars.insert(S[i]); // 记录当前字符swap(S[i], S[begin]);backtracking(S, result, begin 1);swap(S[i], S[begin]);}}
};复杂度分析
通过这种剪枝策略我们避免了搜索重复的路径从而降低了时间复杂度。然而在最坏情况下如所有字符都不同算法的时间复杂度仍然是 O(n!)。空间复杂度与之前的分析相同为 O(n * n!)。虽然这种剪枝策略不能在理论上改进时间复杂度但在有重复字符的情况下实际运行效率会有所提升但是同样每一层都会多创建出一个unordered_set去存储至多n个字符会多消耗一部分的内存空间。
方法三对代码二的再次优化
这一次我们写了一个hasDuplicate函数来检查有没有重复出现的字符。这样就不会使用额外的内存空间去存储字符了。 因为begin的值肯定是要比i小的因为i会递增而begin不会从而我们在这个函数中去递增begin看看有没有会出现与i相当的字符如果出现了就说明有重复就要跳过这个循环
class Solution {
public:vectorstring permutation(string S) {vectorstring result;backtracking(S,result,0);return result;}void backtracking(string S,vectorstring result,int begin){if(begin S.size()) {result.push_back(S);return;}for(int i begin; i S.size(); i){if(hasDuplicate(S,begin,i)) continue;swap(S[i],S[begin]);backtracking(S,result,begin1);swap(S[i],S[begin]);}}bool hasDuplicate(string S, int begin,int end){for(int i begin; i end; i)if(S[i] S[end]) return true;return false;}
};复杂度分析
时间复杂度
permutation 函数的时间复杂度主要取决于 backtracking 函数。在最坏情况下回溯算法将尝试所有可能的排列组合即 n!。hasDuplicate 函数的时间复杂度为 O(n)在 for 循环内部进行比较。backtracking 函数中调用了 hasDuplicate 函数所以在最坏情况下总时间复杂度为 O(n! * n)。
空间复杂度
结果向量 result 的空间复杂度为 O(n!)因为它需要存储所有排列组合。递归栈的空间复杂度为 O(n)因为最深的递归调用次数等于字符串的长度。总的空间复杂度为 O(n! n)。
综上所述该算法的时间复杂度为 O(n! * n)空间复杂度为 O(n! n)。
虽然说代码1,2,3的时间复杂度都是O(n!)但是在代码三的实际时间复杂度要比1,2快了不少。
总结
这道题不算一道特别难的题。但是呢剪枝和去重才是这道题的重中之重。写出简洁并且高效的回溯算法并不容易。我们还得去多学习多总结
