我要招人

去企业版

首页 > 试题广场 >

字符串的全部子序列

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

热度指数：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个相同的子序列

算法知识视频讲解

AimerAimer

发表于 2022-03-06 12:13:01

题意：给定一个字符串s，长度为n，求s的所有子序列 1.子序列: 指一个字符串删掉部分字符（展开全文

牛客348310978号

发表于 2024-06-14 10:12:39

import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param s string字符串 * @retu 展开全文

贪睡的乌龟在攒经验

发表于 2022-09-07 17:03:14

class Solution { public: void sub(string s,int index,string path,set<string> &ans){ //递归函数第一步：想好各个展开全文

认认真真coding

发表于 2022-02-24 22:58:21

字符串的全部子序列题目描述给定一个字符串s，长度为n，求s的所有子序列 1.子序列: 指一个字符串删掉部分字符（也可以不删）形成的字符串，可以是不连续的，比如"abcde"的子序列可以有"ace","ad"等等 2.将所有的子序列的结果返回为一个字符串数组 3.字符串里面可能有重复字符，但是返回展开全文

Ay1n

发表于 2023-11-22 09:17:44

import java.util.*; public class Solution { public static String[] generatePermutation(String str) { Set<String> result = new Ha 展开全文

牛客313925129号

发表于 2022-03-07 16:18:10

题意理解输出一个字符串的所有子串。注意重复出现的子串只保留一个。方法一深度优先搜索每一个字符都有2种情况，选择或者不选择。我们遍历字符串s中的所有字符，每个字符用递归尝试两种调用（选或者不选）。递归的边界条件是遍历到最后一个字符，将得到的子串加入到答案中，然后再回退并进行另一条支路上的递归。展开全文