暴力递归——打印一个字符串的全部子序列

2021-11-11 11:38:16

打印一个字符串的全部子序列

我们先来看看字符串的子串和子序列有什么区别？

字符串的子串：必须是连续的一段

字符串的子序列：可以不连续，但是相对次序不能乱（每个字符要跟不要所有的路都走一遍）——深度优先遍历

看下图，

暴力递归——打印一个字符串的全部子序列

仔细看上边的子序列，是不是就是深度优先遍历呢，哈哈哈。

那么具体如何暴力递归呢，有的时候如果没有思路的话硬写也写不下去，那就只有写一步看一步，如果发现写不下去了，可能是缺少变量啥的，具体分析请看注释。

// 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);
        }
    }
}

暴力递归——打印一个字符串的全部子序列

你学会了吗，????嘻嘻

码农公寓

打印一个字符串的全部子序列

打印一个字符串的全部子序列，要求不要出现重复字面值的子序列

相关文章