题意整理

  • 给定一个字符串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,每个字符有添加和不添加两种选择,总共有2n2^n种选择,所以时间复杂度为O(2n)O(2^n)
  • 空间复杂度:需要额外深度为n的递归栈,所以空间复杂度是O(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()]);
    }
    
}

3.复杂度分析

  • 时间复杂度:假设字符串长度为n,每个字符有添加和不添加两种选择,对应2n2^n个mask位,所以时间复杂度为O(2n)O(2^n)
  • 空间复杂度:需要额外常数级别的空间,所以空间复杂度是O(1)O(1)