本文概述

• 建议：在继续解决方案之前, 请先在{IDE}上尝试使用你的方法。
• C ++
• Python3
• C ++
• Python3

给定一个字符串s，以迭代的方式打印给定字符串的所有可能的子序列。我们已经讨论了打印字符串的所有子序列的递归方法。
例子：

Input : abc Output : a, b, c, ab, ac, bc, abcInput : aab Output : a, b, aa, ab, aab

推荐：请尝试以下方法{IDE}首先, 在继续解决方案之前。 方法1：
这里，我们讨论了更简单的迭代方法，它类似于幂集。我们使用二进制表示1到2^length(s) - 1的比特模式。
【算法（如何实现打印字符串的所有子序列（|迭代法））】input =" abc"
考虑1到(2 ^ 3-1)的二进制表示形式, 即1到7。
从二进制表示形式的左(MSB)到右侧(LSB)开始, 并将与二进制表示形式的位值1相对应的输入字符串中的字符追加到Final子序列字符串sub中。
例子：
001 => abc。只有c对应于比特1。因此, 子序列= c。
101 => abc。 a和c对应于比特1。因此, 子序列= ac。
binary_representation(1)= 001 => c
binary_representation(2)= 010 => b
binary_representation(3)= 011 => bc
binary_representation(4)= 100 => 一个
binary_representation(5)= 101 => 交流
二进制表示(6)= 110 => ab
binary_representation(7)= 111 => abc
下面是上述方法的实现：
C ++

// CPP program to print all Subsequences // of a string in iterative manner #include < bits/stdc++.h> using namespace std; // function to find subsequence string subsequence(string s, int binary, int len) { string sub = "" ; for ( int j = 0; j < len; j++)// check if jth bit in binary is 1 if (binary & (1 < < j))// if jth bit is 1, include it // in subsequence sub += s[j]; return sub; }// function to print all subsequences void possibleSubsequences(string s){// map to store subsequence // lexicographically by length map< int , set< string> > sorted_subsequence; int len = s.size(); // Total number of non-empty subsequence // in string is 2^len-1 int limit = pow (2, len); // i=0, corresponds to empty subsequence for ( int i = 1; i < = limit - 1; i++) { // subsequence for binary pattern i string sub = subsequence(s, i, len); // storing sub in map sorted_subsequence[sub.length()].insert(sub); }for ( auto it : sorted_subsequence) { // it.first is length of Subsequence // it.second is set< string> cout < < "Subsequences of length = " < < it.first < < " are:" < < endl; for ( auto ii : it.second)// ii is iterator of type set< string> cout < < ii < < " " ; cout < < endl; } }// driver function int main() { string s = "aabc" ; possibleSubsequences(s); return 0; }

Python3

# Python3 program to print all Subsequences # of a string in iterative manner# function to find subsequence def subsequence(s, binary, length): sub = "" for j in range (length):# check if jth bit in binary is 1 if (binary & ( 1 < < j)):# if jth bit is 1, include it # in subsequence sub + = s[j] return sub# function to print all subsequences def possibleSubsequences(s):# map to store subsequence # lexicographically by length sorted_subsequence = {}length = len (s)# Total number of non-empty subsequence # in string is 2^len-1 limit = 2 * * length# i=0, corresponds to empty subsequence for i in range ( 1 , limit):# subsequence for binary pattern i sub = subsequence(s, i, length)# storing sub in map if len (sub) in sorted_subsequence.keys(): sorted_subsequence[ len (sub)] = \ tuple ( list (sorted_subsequence[ len (sub)]) + [sub]) else : sorted_subsequence[ len (sub)] = [sub]for it in sorted_subsequence:# it.first is length of Subsequence # it.second is set< string> print ( "Subsequences of length =" , it, "are:" ) for ii in sorted ( set (sorted_subsequence[it])):# ii is iterator of type set< string> print (ii, end = ' ' ) print ()# Driver Code s = "aabc" possibleSubsequences(s)# This code is contributed by ankush_953

输出如下：

Subsequences of length = 1 are: a b c Subsequences of length = 2 are: aa ab ac bc Subsequences of length = 3 are: aab aac abc Subsequences of length = 4 are: aabc

时间复杂度：

文章图片
, 其中n是查找子序列的字符串的长度, l是二进制字符串的长度。
方法2：
方法是获取最右边的设置位的位置, 并在将给定字符串中的相应字符附加到子序列后重置该位, 并将重复相同的操作, 直到相应的二进制模式没有设置位为止。
如果输入为s =" abc"
考虑1到(2 ^ 3-1)的二进制表示形式, 即1到7。
001 => abc。只有c对应于比特1。因此, 子序列= c
101 => abc。 a和c对应于比特1。因此, 子序列= ac。
让我们使用5的二进制表示形式, 即101。
最右边的位在位置1, 在sub = c的开头附加字符, 重置位置1 => 100
最右边的位在位置3, 在sub = ac的开头附加字符, 重置位置3 => 000
由于现在我们没有剩余的设置位, 因此我们将停止计算子序列。
范例：
binary_representation(1)= 001 => c
binary_representation(2)= 010 => b
binary_representation(3)= 011 => bc
binary_representation(4)= 100 => 一个
binary_representation(5)= 101 => 交流
二进制表示(6)= 110 => ab
binary_representation(7)= 111 => abc
下面是上述方法的实现：
C ++

// CPP code all Subsequences of a // string in iterative manner #include < bits/stdc++.h> using namespace std; // function to find subsequence string subsequence(string s, int binary) { string sub = "" ; int pos; // loop while binary is greater than 0 while (binary> 0) { // get the position of rightmost set bit pos=log2(binary& -binary)+1; // append at beginning as we are // going from LSB to MSB sub=s[pos-1]+sub; // resets bit at pos in binary binary= (binary & ~(1 < < (pos-1))); } reverse(sub.begin(), sub.end()); return sub; }// function to print all subsequences void possibleSubsequences(string s){// map to store subsequence // lexicographically by length map< int , set< string> > sorted_subsequence; int len = s.size(); // Total number of non-empty subsequence // in string is 2^len-1 int limit = pow (2, len); // i=0, corresponds to empty subsequence for ( int i = 1; i < = limit - 1; i++) { // subsequence for binary pattern i string sub = subsequence(s, i); // storing sub in map sorted_subsequence[sub.length()].insert(sub); }for ( auto it : sorted_subsequence) { // it.first is length of Subsequence // it.second is set< string> cout < < "Subsequences of length = " < < it.first < < " are:" < < endl; for ( auto ii : it.second)// ii is iterator of type set< string> cout < < ii < < " " ; cout < < endl; } }// driver function int main() { string s = "aabc" ; possibleSubsequences(s); return 0; }

Python3

# Python3 program to print all Subsequences # of a string in an iterative manner from math import log2, floor# function to find subsequence def subsequence(s, binary): sub = ""# loop while binary is greater than while (binary > 0 ):# get the position of rightmost set bit pos = floor(log2(binary& - binary) + 1 )# append at beginning as we are # going from LSB to MSB sub = s[pos - 1 ] + sub# resets bit at pos in binary binary = (binary & ~( 1 < < (pos - 1 )))sub = sub[:: - 1 ] return sub# function to print all subsequences def possibleSubsequences(s):# map to store subsequence # lexicographically by length sorted_subsequence = {}length = len (s)# Total number of non-empty subsequence # in string is 2^len-1 limit = 2 * * length# i=0, corresponds to empty subsequence for i in range ( 1 , limit):# subsequence for binary pattern i sub = subsequence(s, i)# storing sub in map if len (sub) in sorted_subsequence.keys(): sorted_subsequence[ len (sub)] = \ tuple ( list (sorted_subsequence[ len (sub)]) + [sub]) else : sorted_subsequence[ len (sub)] = [sub]for it in sorted_subsequence:# it.first is length of Subsequence # it.second is set< string> print ( "Subsequences of length =" , it, "are:" ) for ii in sorted ( set (sorted_subsequence[it])):# ii is iterator of type set< string> print (ii, end = ' ' ) print ()# Driver Code s = "aabc" possibleSubsequences(s)# This code is contributed by ankush_953

输出如下：

Subsequences of length = 1 are: a b c Subsequences of length = 2 are: aa ab ac bc Subsequences of length = 3 are: aab aac abc Subsequences of length = 4 are: aabc

时间复杂度：

文章图片
, 其中n是找到子序列的字符串的长度, b是二进制字符串中设置的位数。

推荐阅读

• 

  有哪些专业的笔记本电脑检测软件？
• 

  韩妙面膜有荧光剂吗
• 

  新人如何选择第一份工作
• 

  无线投屏怎么连接电视 无线投屏如何连接电视
• 

  网络视频用户分析,2022年中国网络视频用户规模
• 

  荔枝吃多了会流鼻血吗
• 

  三国志哪个版本最有可玩性？
• 

  鸡蛋会引起胀气吗
• 

  天凉后老年人注意背部保暖
• 

  孩子性早熟有哪些表现 五岁孩子性早熟有哪些表现
• 

  肾虚吃什么？？
• 

  我的世界怎么换材质包手机版老版本 我的世界国际版如何更改材质
• 

  苹果11跟苹果Xr区别是什么苹果11跟苹果Xr区别是啥
• 

  jquery插件（三）（Colorbox–内容播放插件）
• 

  圆通快递费怎么算 圆通快递运费是多少
• 

  葡萄和虾能一起吃吗
• 

  15秒风景视频无水印 最美的图片和风景 大自然
• 

  关于民族团结的句子
• 

  索尼爱立信st25i手机，索尼爱立信st21i
• 

  冰箱变温区是什么？如何正确使用和维护？

• Python程序如何实现在列表中打印正数（）
• Numpy字符串运算详细教程指南
• 云计算的特点简要介绍
• 基于类的通用视图Django（创建，检索，更新，删除）
• PHP如何使用SplDoublyLinkedList add()函数（）
• 算法（如何计算每个字符至少出现k次的最长子序列（））
• 本图文详细教程教你win10企业版激活
• 本图文详细教程教你Win10如何更改帐户名称
• 本图文详细教程教你Win10如何把常用设置项固定到开始菜