字符串的全部子序列

[编程题]字符串的全部子序列

热度指数：3664 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个字符串s，长度为n，求s的所有子序列

1.子序列: 指一个字符串删掉部分字符（也可以不删）形成的字符串，可以是不连续的，比如"abcde"的子序列可以有"ace","ad"等等

2.将所有的子序列的结果返回为一个字符串数组

3.字符串里面可能有重复字符，但是返回的子序列不能有重复的子序列，比如"aab"的子序列只有"","a","aa","aab","ab","b"，不能存在2个相同的"ab"

4.返回字符串数组里面的顺序可以不唯一

数据范围:

$0<=s.length<=16$

要求:时间复杂度为 $O(2^n)$

示例1

输入

"ab"

输出

["","a","ab","b"]

说明

返回["","b","a","ab"]也是可以的，视为正确，顺序不唯一

示例2

输入

"dbcq"

输出

["","b","bc","bcq","bq","c","cq","d","db","dbc","dbcq","dbq","dc","dcq","dq","q"]

示例3

输入

"aab"

输出

["","a","aa","aab","ab","b"]

说明

返回的字符串数组里面不能存在"ab","ab"这样2个相同的子序列

算法知识视频讲解

小谷围做题家

package main
import _"fmt"

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param s string字符串 
 * @return string字符串一维数组
*/
func generatePermutation( s string ) []string {
    ans:=[]string{}
    vis:=map[string]bool{}
    var back_tracking func(string,int)
    back_tracking=func(path string,idx int){
        if _,ok:=vis[path];!ok{
            ans=append(ans,path)
            vis[path]=true
        }
        for i:=idx;i<len(s);i++{
            path+=string(s[i])
            back_tracking(path,i+1)
            path=path[:len(path)-1]
        }
    }
    back_tracking("",0)
    return ans
}

发表于 2023-03-09 23:25:18 回复(0)