题解 | #字符串的全部子序列#

字符串的全部子序列

题目描述 给定一个字符串s，长度为n，求s的所有子序列

1.子序列: 指一个字符串删掉部分字符（也可以不删）形成的字符串，可以是不连续的，比如"abcde"的子序列可以有"ace","ad"等等

2.将所有的子序列的结果返回为一个字符串数组

3.字符串里面可能有重复字符，但是返回的子序列不能有重复的子序列，比如"aab"的子序列只有"","a","aa","aab","ab","b"，不能存在2个相同的"ab"

4.返回字符串数组里面的顺序可以不唯一

方法一：递归的方法

解题思路

对于本题，使用递归的方法，对于每个位置的字符可以选择也可以不选择，不选择的情况则子序列从下个字符开始，然后向后递归，这样得到所有子序列，然后去除重复的子序列，最后得到答案。

解题代码

class Solution {
public:
    void dfs(string s,int idx,string curs,vector<string> & arr)
    {
        if(idx == s.length())
        { // 长度
            arr.emplace_back(curs);
            return ;
        }
        dfs(s,idx+1,curs,arr); // 不选择
        dfs(s,idx+1,curs+s[idx],arr); // 选择
    }
    vector<string> generatePermutation(string s)
    {
        vector<string> arr;
        dfs(s,0,"",arr);
        sort(arr.begin(), arr.end()); // 排序
        arr.erase(unique(arr.begin(), arr.end()), arr.end()); // 去重
        return arr;
    }
};

复杂度分析

时间复杂度：时间花费在产生子序列以及子序列的排序，因此时间复杂度为$O(n\ast 2^n)O(n*2^n)$。

空间复杂度：主要消耗在生产的结果上，因此空间复杂度为$O(2^n)O(2^n)$。

方法二：优化的方法

解题思路

方法一中最后进行排序去重，因此考虑使用set来记录出现过的字符，进而来优化时间复杂度。

解题代码

class Solution {
public:
    void dfs(string s,int idx,string curs,vector<string> & arr,set<string> & strSet)
    {
        if(idx == s.length())
        { // 取完字符串
            if(!strSet.count(curs))
            { // 防止重复
                strSet.insert(curs); // 记录出现过
                arr.emplace_back(curs); // 加入到数组
            }
            return ;
        }
        dfs(s,idx+1,curs,arr,strSet); // 不取当前字符
        dfs(s,idx+1,curs + s[idx],arr,strSet); // 取当前字符
    }
    vector<string> generatePermutation(string s)
    {
        vector<string> arr; // 结果
        set<string> strSet; // 辅助记录出现情况
        dfs(s,0,"",arr,strSet);
        return arr;
    }
};

复杂度分析

时间复杂度：主要消耗在产生子序列，因此时间复杂度为$O(2^n)O(2^n)$。

空间复杂度：产生子序列需要申请额外的内存地址空间，因此空间复杂度为$O(2^n)O(2^n)$。