题意理解

输出一个字符串的所有子串。注意重复出现的子串只保留一个。

方法一

深度优先搜索
每一个字符都有2种情况,选择或者不选择。我们遍历字符串s中的所有字符,每个字符用递归尝试两种调用(选或者不选)。递归的边界条件是遍历到最后一个字符,将得到的子串加入到答案中,然后再回退并进行另一条支路上的递归。

深度优先搜索的示意图如下,字符串为"ab",边上"0"表示不选,"1"表示选: alt

最后对包含了所有答案的数组进行排序并去重。

具体代码如下:

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @return string字符串vector
     */
    vector<string> ans;
    void dfs(string s, int k, string sub) {
        if (k==s.size())
        {
            ans.push_back(sub);
            return;
        }
        //当前字符不加入子串
        dfs(s, k+1, sub);
        //当前字符加入子串
        dfs(s, k+1, sub+s[k]);
        return;
    }
    
    vector<string> generatePermutation(string s) {
        // write code here
        dfs(s, 0, "");
        //排序并删除重复子串
        sort(ans.begin(), ans.end());
        ans.erase(unique(ans.begin(), ans.end()), ans.end());
        return ans;
    }
};

时间复杂度: O(2Nlog2N)O(2^N*\log{{2^N}})。一共有2N2^N种情况,对所有的情况进行一次快排,N为字符串长度。
空间复杂度: O(2N)O(2^N)。开辟了新的空间存储最终答案,一共有2N2^N个子串。

方法二

优化
我们使用map<string,bool>类型的变量来记录某个子串是否已经出现过。

具体代码如下:

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @return string字符串vector
     */
    unordered_map<string, bool> get;
    vector<string> ans;
    void dfs(string s, int k, string sub) {
        if (k==s.size())
        {
            if (get.find(sub)==get.end())
            {
                get[sub] = true;
                ans.push_back(sub);
            }
            return;
        }
        dfs(s, k+1, sub);
        dfs(s, k+1, sub+s[k]);
        return;
    }
    
    vector<string> generatePermutation(string s) {
        // write code here
        dfs(s, 0, "");
        return ans;
    }
};

时间复杂度: O(2N)O(2^N)。一共有2N2^N种情况,每个情况都要判断是否已经提取出来了。N为字符串长度。
空间复杂度: O(2N)O(2^N)。开辟了新的空间记录某个子串是否出现过,以及存储最终答案,一共有2N2^N个子串。

方法二