本文概述

• 建议：在继续解决方案之前, 请先在{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是二进制字符串中设置的位数。

推荐阅读

• 

  个人所得税怎么添加残疾证享受税收优惠?个人所得税添加残疾证的操作步骤
• 

  佳能60d怎么用液晶屏拍照 佳能60d怎么用
• 

  梦见脸盆漏水是啥意思 梦见脸盆漏了
• 

  redis的中文翻译 redis在线翻译
• 

  无花果叶子煮水的功效与作用 无花果叶泡水喝的禁忌
• 

  pptv手机配置怎么样 PPTV手机配置怎么样?
• 

  壁挂炉林内不烧热水解决方法
• 

  火腿肉能放多久
• 

  华为mate信号很差怎么办
• 

  安卓手机硬件组成,手持终端需具备哪些特征?
• 

  sas 文本分析,SAS文本分析
• 

  肉薄骨并是什么意思啊 成语肉薄骨并是什么意思
• 

  易信怎么设置聊天背景_易信聊天背景设置方法介绍
• 

  清集镇中心校校长王锦枝到苇元小学视察工作
• 

  男生一般喜欢穿什么鞋？
• 

  新征程是指什么时间
• 

  斯柯达epc亮发动机抖动? 车epc和发动机故障灯亮车辆抖动
• 

  龙潭湖灯会 什么时候 2023天河潭元宵灯会开放时间
• 

  张桂梅事迹简单介绍 张桂梅是谁
• 

  i3cpu升级什么cpu，笔记本i3cpu升级cpu

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