0字符串中等 NC190 字符串的全部子序列

0字符串中等 NC190 字符串的全部子序列

NC190 字符串的全部子序列

描述

给定一个字符串s，长度为n，求s的所有子序列
1.子序列: 指一个字符串删掉部分字符（也可以不删）形成的字符串，可以是不连续的，比如"abcde"的子序列可以有"ace",“ad"等等
2.将所有的子序列的结果返回为一个字符串数组
3.字符串里面可能有重复字符，但是返回的子序列不能有重复的子序列，比如"aab"的子序列只有”",“a”,“aa”,“aab”,“ab”,“b”，不能存在2个相同的"ab"
4.返回字符串数组里面的顺序可以不唯一

网友的代码：

每个字符有两个选择，选或者不选。

import java.util.*;
public class Solution {HashSet<String>set;public String[] generatePermutation (String s) {set = new HashSet<>();dfs(s,0,"");Array(new String[0]);}public void dfs(String s, int index, String str){if (index==s.length()){set.add(str);return;}dfs(s,index+1,str+s.charAt(index));dfs(s,index+1,str);}
}

回溯

• 回溯穷尽所有子序列的可能
• StringBuffer有deleteCharAt()方法，可以删除指定位置的字符

import java.util.*;
public class Solution {Set<String> set = new HashSet<>();public String[] generatePermutation (String s) {backTrace(s,0,new StringBuffer());String[] ans = new String[set.size()+1];int i = 0;for(String str : set){ans[i++] = str;}ans[set.size()] = "";return ans;}public void backTrace(String s, int index, StringBuffer sb){if(index == s.length()){return ;}for(int i = index; i < s.length(); i++){sb.append(s.charAt(i));set.String());backTrace(s,i+1,sb); sb.deleteCharAt(sb.length()-1);}}
}