打印一个字符串的全部子序列
我们先来看看字符串的子串和子序列有什么区别？
字符串的子串：必须是连续的一段
字符串的子序列：可以不连续，但是相对次序不能乱（每个字符 要跟不要 所有的路都走一遍）——深度优先遍历
看下图，
仔细看上边的子序列，是不是就是深度优先遍历呢，哈哈哈。
那么具体如何暴力递归呢，有的时候如果没有思路的话硬写也写不下去，那就只有写一步看一步，如果发现写不下去了，可能是缺少变量啥的，具体分析请看注释。
// str 固定不变的字符串 // index此时来到的位置 要或者不要，做选择 // ans 如果index来到了str中的终止位置，把沿途路径所形成的答案放入ans中 // path 之前做出的选择 public static void process1(char[] str,int index,List<String> ans,String path) { // 如果index来到了字符串的最后一个位置 // 只需要把沿途路径加入ans,然后返回 if(index==str.length) { ans.add(path); return ; } // 如果没有来到最后一个位置，就要考虑要不要index位置的字符 // 不要index位置的字符，往下做选择 String no=path; process1(str, index+1, ans, no); // 要index位置的字符，往下做选择 String yes=path+String.valueOf(str[index]); process1(str, index+1, ans, yes); } public static List<String> printAllSubsequences(String s){ char[] str=s.toCharArray(); List<String> ans=new LinkedList<>(); String path=""; process1(str, 0, ans, path); return ans; }
现在我们把题目改一下，如果价格条件，要去重，题目变为：
打印一个字符串的全部子序列，要求不要出现重复字面值的子序列
上面举的例子是字符串abc，如果是字符串aaa呢，是不是肯定有字面值重复的子序列。
解决办法：递归方式还是一样，只需要把原先用来装答案的容器改为HashSet就可以，其它都一样，因为集合可以自动去重。主方法调用也需要改一下，返回的时候遍历集合，放入List后再返回结果就可以了。
public static void process2(char[] str,int index,HashSet<String> ans,String path) { if(index==str.length) { ans.add(path); return ; } String no=path; process2(str, index+1, ans, no); String yes=path+String.valueOf(str[index]); process2(str, index+1, ans, yes); } public static List<String> printNoRepeat(String s){ char[] str=s.toCharArray(); HashSet<String> set=new HashSet<>(); String path=""; process2(str, 0, set, path); List<String> ans=new ArrayList<>(); for(String cur:set) { ans.add(cur); } return ans; }
如果题目要求不用打印所有字面值不重复的子序列，而是只需要知道所有字面值不重复的子序列的个数，那么这其实是一个经典的动态规划问题，博主后序文章一定会写到的，这篇文章就到这啦，感谢你的三连或者点赞支持🙇🙇🙇
最后附上完整代码：
package com.harrison.class12; import java.util.ArrayList; import java.util.HashSet; import java.util.List; public class Code03_PrintAllSubsequences { // str 固定不变的字符串 // index此时来到的位置 要或者不要，做选择 // ans 如果index来到了str中的终止位置，把沿途路径所形成的答案放入ans中 // path 之前做出的选择 public static void process1(char[] str,int index,List<String> ans,String path) { // 如果index来到了字符串的最后一个位置 // 只需要把沿途路径加入ans,然后返回 if(index==str.length) { ans.add(path); return ; } // 如果没有来到最后一个位置，就要考虑要不要index位置的字符 // 不要index位置的字符，往下做选择 String no=path; process1(str, index+1, ans, no); // 要index位置的字符，往下做选择 String yes=path+String.valueOf(str[index]); process1(str, index+1, ans, yes); } public static List<String> printAllSubsequences(String s){ char[] str=s.toCharArray(); List<String> ans=new ArrayList<>(); String path=""; process1(str, 0, ans, path); return ans; } public static void process2(char[] str,int index,HashSet<String> ans,String path) { if(index==str.length) { ans.add(path); return ; } String no=path; process2(str, index+1, ans, no); String yes=path+String.valueOf(str[index]); process2(str, index+1, ans, yes); } public static List<String> printNoRepeat(String s){ char[] str=s.toCharArray(); HashSet<String> set=new HashSet<>(); String path=""; process2(str, 0, set, path); List<String> ans=new ArrayList<>(); for(String cur:set) { ans.add(cur); } return ans; } public static void main(String[] args) { String test="accc"; List<String> ans1=printAllSubsequences(test); List<String> ans2=printNoRepeat(test); for(String str:ans1) { System.out.println(str); } System.out.println("===================="); for(String str:ans2) { System.out.println(str); } } }
你学会了吗，🤭嘻嘻
