题解 | #字符串的全部子序列#

字符串的全部子序列

http://www.nowcoder.com/practice/92e6247998294f2c933906fdedbc6e6a

题意整理

给定一个字符串s，长度为n，求s的所有子序列。
如果子序列重复，则只添加一次。

方法一（回溯）

1.思路整理

首先将字符串转化为字符数组。
然后对字符数组进行遍历，每一个字符要么添加、要么不添加，利用回溯法添加字符数组中所有可能的字符组合，每一个组合代表一个子序列。每完成一轮添加，将对应组合加入到结果集。

2.代码实现

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @return string字符串一维数组
     */
    //用set记录，防止重复添加
    Set<String> res=new HashSet<>();
    public String[] generatePermutation (String s) {
        //转化为字符数组
        char[] arr=s.toCharArray();
        //回溯
        dfs(arr,new StringBuilder(),0);
        return res.toArray(new String[res.size()]);
    }
    
    private void dfs(char[] arr,StringBuilder sb,int index){
        res.add(sb.toString());
        for(int i=index;i<arr.length;i++){
            //添加当前字符
            sb.append(arr[i]);
            //对下一位进行递归
            dfs(arr,sb,i+1);
            //回退到不添加的状态
            sb.deleteCharAt(sb.length()-1);
        }
    }
}

3.复杂度分析

时间复杂度：假设字符串长度为n，每个字符有添加和不添加两种选择，总共有 $2^{n}$ 种选择，所以时间复杂度为 $O (2^{n})$ 。
空间复杂度：需要额外深度为n的递归栈，所以空间复杂度是 $O (n)$ 。

方法二（位运算）

1.思路整理

定义一个长度为n的二进制mask位。每一个mask对应一个子序列，mask对应位置为0，表示不选择当前字符，为1表示选择当前字符。只要遍历所有的mask位，就可以将所有的子序列加入到结果集。

图解展示： alt

2.代码实现

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @return string字符串一维数组
     */
    
    public String[] generatePermutation (String s) {
        //转化为字符数组
        char[] arr=s.toCharArray();
        int n=arr.length;
        //使用set存储，防止重复添加
        Set<String> res=new HashSet<>();
        //遍历所有mask位
        for(int mask=0;mask<(1<<n);mask++){
            StringBuilder sb=new StringBuilder();
            for(int i=0;i<n;i++){
                if((mask&(1<<i))!=0){
                    sb.append(arr[i]);
                }
            }
            //填加mask对应子序列
            res.add(sb.toString());
        }
        return res.toArray(new String[res.size()]);
    }
    
}