题解 | #字符串的全部子序列#
字符串的全部子序列
http://www.nowcoder.com/practice/92e6247998294f2c933906fdedbc6e6a
题意：
给定一个字符串s，长度为n，求s的所有子序列
1.子序列: 指一个字符串删掉部分字符（也可以不删）形成的字符串，可以是不连续的，比如"abcde"的子序列可以有"ace","ad"等等
2.将所有的子序列的结果返回为一个字符串数组
3.字符串里面可能有重复字符，但是返回的子序列不能有重复的子序列，比如"aab"的子序列只有"","a","aa","aab","ab","b"，不能存在2个相同的"ab"
4.返回字符串数组里面的顺序可以不唯一
方法一：
递归回溯
思路：递归回溯题型，先画图再写代码。
递归，每一层表示一个字符，针对每个字符有两种选择：不取 或 取。即可得到所以的子序列，最后去重即可。
class Solution {
public:
int len;
vector<string> res;
vector<string> generatePermutation(string s) {
len=s.size();
dfs(s,"",0);//递归回溯
sort(res.begin(),res.end());//排序
res.erase(unique(res.begin(),res.end()),res.end());//取重
return res;
}
void dfs(string s,string x,int cur){//递归回溯
if(cur==len){
res.push_back(x);
return;
}
dfs(s,x,cur+1);//不取
dfs(s,x+s[cur],cur+1);//取
}
};
时间复杂度：%2Cn%E6%98%AF%E5%AD%97%E7%AC%A6%E4%B8%B2%E7%9A%84%E9%95%BF%E5%BA%A6%EF%BC%8C%E6%AF%8F%E4%B8%AA%E5%AD%97%E7%AC%A6%E6%9C%89%E4%B8%8D%E5%8F%96%E5%92%8C%E5%8F%96%E4%B8%A4%E7%A7%8D%E9%80%89%E6%8B%A9%E3%80%82)
空间复杂度：%2C%E9%80%92%E5%BD%92%E6%A0%88%E7%9A%84%E6%B7%B1%E5%BA%A6%E3%80%82)
方法二：
map优化
思路：针对方法一的优化：
初始化无序map判断字符串是否存在。如果字符串不存在，则加入结果数组；如果已存在，则不加入结果数组。
class Solution {
public:
int len;
vector<string> res;
unordered_map<string,int> mp;//判断字符串是否存在
vector<string> generatePermutation(string s) {
len=s.size();
dfs(s,"",0);//递归回溯
return res;
}
void dfs(string s,string x,int cur){//递归回溯
if(cur==len){
if(!mp.count(x)){//如果字符串不存在，则加入结果数组
res.push_back(x);
mp[x]=1;
}
return;
}
dfs(s,x,cur+1);//不取
dfs(s,x+s[cur],cur+1);//取
}
};
时间复杂度：空间复杂度：%2C%E9%80%92%E5%BD%92%E6%A0%88%E7%9A%84%E6%B7%B1%E5%BA%A6%E5%92%8C%E5%AD%98%E5%82%A8%E6%97%A0%E5%BA%8Fmap%E3%80%82)
