随笔记录

算法-字符串全部子序列

2022-4-21 diaba 算法

package com.jiucaiyuan.net.question;

import java.util.ArrayList;
import java.util.List;

/**
 * 【问题】打印一个字符串的全部子序列，包含空字符串
 * 【思路】从第一个字符开始，逐个字符进行处理，每个字符都可以选择要还是不要，分两条路递归
 *
 * @Author jiucaiyuan  2022/4/20 23:57
 * @mail services@jiucaiyuan.net
 */

public class PrintAllSubSequence {
    /**
     * 使用数组本身，最后还原
     *
     * @param str
     */
    public static void printAllSubSequence(String str) {
        char[] chs = str.toCharArray();
        process(chs, 0);
    }

    /**
     * 当前来到i这个位置，要和不要，走两条路，
     * 使用数组本身，最后还原
     *
     * @param chs 之前的选择所形成的的结果
     * @param i   当前这个位置
     */
    private static void process(char[] chs, int i) {
        if (i == chs.length) {
            printArray(chs);
            return;
        }
        process(chs, i + 1); //要当前i的字符
        char temp = chs[i];
        chs[i] = 0;
        process(chs, i + 1); //不要当前i的字符
        chs[i] = temp;
    }

    /**
     * 费额外空间
     *
     * @param str
     */
    public static void function(String str) {
        char[] chs = str.toCharArray();
        process(chs, 0, new ArrayList<Character>());
    }

    /**
     * 走到当前i的位置，包含要和不要两条路
     * 费额外空间
     *
     * @param chs chs 所有字符
     * @param i   处理当前i位置的字符
     * @param res 之前的选择
     */
    private static void process(char[] chs, int i, List<Character> res) {
        if (i == chs.length) {
            printList(res);
            return;
        }
        List<Character> resKeep = copyList(res);
        resKeep.add(chs[i]);
        process(chs, i + 1, resKeep);
        List<Character> resNoInclude = copyList(res);
        process(chs, i + 1, resNoInclude);
    }

    private static List<Character> copyList(List<Character> res) {
        List<Character> result = new ArrayList<>();
        for (Character ch : res) {
            result.add(ch);
        }
        return result;
    }

    private static void printArray(char[] chs) {
        for (char ch : chs) {
            if (0 != ch) {
                System.out.print(ch);
            }
        }
        System.out.println();
    }

    private static void printList(List<Character> res) {
        for (char ch : res) {
            if (0 != ch) {
                System.out.print(ch);
            }
        }
        System.out.println();
    }

    public static void main(String[] args) {
        String str = "abc";
        printAllSubSequence(str);
        function(str);
    }
}