字符串的全部子序列

题意

给一个字符串，求它的字符串的全部子序列

方法

递归生成所有序列并排序去重

分析

子序列不能改变字符的顺序，但是可以不连续

于是实际上相当于字符串中选取部分字符，然后保持原有的顺序拼接而成

考虑递归每一个深度分别选择当前位置字符和不选择当前位置字符, 并向下递归

这样就能得到所有的子序列

但题目要求重复的子序列只出现一次，考虑使用排序去重

代码

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); // 选择
    }
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @return string字符串vector
     */
    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(2^n)O(2^n)$

时间复杂度: 主要代价为产生所有子序列,和产生后的排序，所以总时间复杂度为$O(n\cdot 2^n)O(n\backslash cdot\; 2^n)$

递归+set/字典树

分析

上面的方法在找到每个字符串的时候，并没有处理去重，而是最后才做的去排序去重

考虑使用字典树，或者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); // 取当前字符
    }
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @return string字符串vector
     */
    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)$