按字典顺序生成给定字符串的不同子序列-yiteyi-C++库

给定一个字符串s，列出给定字符串s的所有可能字母组合。如果有两个字符串具有相同的字符集，则打印两个字符串的最小字典排列对于字符串abc，按字典顺序排列的子序列是，a ab abc ac b bc c 例如：

null

Input : s = "ab"Output : a ab bInput  : xyzxOutput : x xx xy xyx xyz xyzx xz xzx y         yx yz yzx z zx

推荐：请尝试你的方法 {IDE} 首先，在进入解决方案之前。

其思想是使用一个集合（使用自平衡BST )存储子序列，以便测试副本。为了生成所有的子序列，我们一个接一个地删除每个字符，并重复生成剩余的字符串。

C++

                         // C++ program to print all distinct subsequences                       
                         // of a string.                       
                         #include <bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                         // Finds and stores result in st for a given                       
                         // string s.                       
                         void                                     generate(set<string>& st, string s)                       
                         {                       
                                                 if                                     (s.size() == 0)                       
                                                 return                                     ;                       
           
                                                 // If current string is not already present.                       
                                                 if                                     (st.find(s) == st.end()) {                       
                                                 st.insert(s);                       
           
                                                 // Traverse current string, one by one                       
                                                 // remove every character and recur.                       
                                                 for                                     (                                     int                                     i = 0; i < s.size(); i++) {                       
                                                 string t = s;                       
                                                 t.erase(i, 1);                       
                                                 generate(st, t);                       
                                                 }                       
                                                 }                       
                                                 return                                     ;                       
                         }                       
           
                         // Driver code                       
                         int                                     main()                       
                         {                       
                                                 string s =                                     "xyz"                                     ;                       
                                                 set<string> st;                       
                                                 set<string>::iterator it;                       
                                                 generate(st, s);                       
                                                 for                                     (                                     auto                                     it = st.begin(); it != st.end(); it++)                       
                                                 cout << *it << endl;                       
                                                 return                                     0;                       
                         }                       

JAVA

                         // Java program to print all distinct subsequences                       
                         // of a string.                       
                         import                                     java.util.*;                       
           
                         class                                     GFG {                       
           
                                                 // Finds and stores result in st for a given                       
                                                 // string s.                       
                                                 static                                     void                                     generate(Set<String> st, String s)                       
                                                 {                       
                                                 if                                     (s.length() ==                                     0                                     ) {                       
                                                 return                                     ;                       
                                                 }                       
           
                                                 // If current string is not already present.                       
                                                 if                                     (!st.contains(s)) {                       
                                                 st.add(s);                       
           
                                                 // Traverse current string, one by one                       
                                                 // remove every character and recur.                       
                                                 for                                     (                                     int                                     i =                                     0                                     ; i < s.length(); i++) {                       
                                                 String t = s;                       
                                                 t = t.substring(                                     0                                     , i) + t.substring(i +                                     1                                     );                       
                                                 generate(st, t);                       
                                                 }                       
                                                 }                       
                                                 return                                     ;                       
                                                 }                       
           
                                                 // Driver code                       
                                                 public                                     static                                     void                                     main(String args[])                       
                                                 {                       
                                                 String s =                                     "xyz"                                     ;                       
                                                 TreeSet<String> st =                                     new                                     TreeSet<>();                       
                                                 generate(st, s);                       
                                                 for                                     (String str : st) {                       
                                                 System.out.println(str);                       
                                                 }                       
                                                 }                       
                         }                       
           
                         // This code has been contributed by 29AjayKumar                       
                         // modified by rahul_107                       

Python 3

                         # Python program to print all distinct                       
                         # subsequences of a string.                       
           
                         # Finds and stores result in st for a given                       
                         # string s.                       
                         def                                     generate(st, s):                       
                                                 if                                     len                                     (s)                                     =                                     =                                     0                                     :                       
                                                 return                       
           
                                                 # If current string is not already present.                       
                                                 if                                     s                                     not                                     in                                     st:                       
                                                 st.add(s)                       
           
                                                 # Traverse current string, one by one                       
                                                 # remove every character and recur.                       
                                                 for                                     i                                     in                                     range                                     (                                     len                                     (s)):                       
                                                 t                                     =                                     list                                     (s).copy()                       
                                                 t.remove(s[i])                       
                                                 t                                     =                                     ''.join(t)                       
                                                 generate(st, t)                       
           
                                                 return                       
           
           
                         # Driver Code                       
                         if                                     __name__                                     =                                     =                                     "__main__"                                     :                       
                                                 s                                     =                                     "xyz"                       
                                                 st                                     =                                     set                                     ()                       
                                                 generate(st, s)                       
                                                 for                                     i                                     in                                     st:                       
                                                 print                                     (i)                       
           
                         # This code is contributed by                       
                         # sanjeev2552                       

C#

                         // C# program to print all distinct subsequences                       
                         // of a string.                       
                         using                                     System;                       
                         using                                     System.Collections.Generic;                       
           
                         class                                     GFG {                       
           
                                                 // Finds and stores result in st for a given                       
                                                 // string s.                       
                                                 static                                     void                                     generate(HashSet<String> st, String s)                       
                                                 {                       
                                                 if                                     (s.Length == 0) {                       
                                                 return                                     ;                       
                                                 }                       
           
                                                 // If current string is not already present.                       
                                                 if                                     (!st.Contains(s)) {                       
                                                 st.Add(s);                       
           
                                                 // Traverse current string, one by one                       
                                                 // remove every character and recur.                       
                                                 for                                     (                                     int                                     i = 0; i < s.Length; i++) {                       
                                                 String t = s;                       
                                                 t = t.Substring(0, i) + t.Substring(i + 1);                       
                                                 generate(st, t);                       
                                                 }                       
                                                 }                       
                                                 return                                     ;                       
                                                 }                       
           
                                                 // Driver code                       
                                                 public                                     static                                     void                                     Main(String[] args)                       
                                                 {                       
                                                 String s =                                     "xyz"                                     ;                       
                                                 HashSet<String> st =                                     new                                     HashSet<String>();                       
                                                 generate(st, s);                       
                                                 foreach                                     (String str                                     in                                     st)                       
                                                 {                       
                                                 Console.WriteLine(str);                       
                                                 }                       
                                                 }                       
                         }                       
           
                         /* This code contributed by PrinciRaj1992 */                       

Javascript

                         <script>                       
           
                         // JavaScript program to print                       
                         // all distinct subsequences                       
                         // of a string.                       
           
                         // Finds and stores result in st for a given                       
                         // string s.                       
                         function                                     generate(st,s){                       
                                                 if                                     (s.length == 0)                       
                                                 return                                     st;                       
           
                                                 // If current string is not already present.                       
                                                 if                                     (!st.has(s)) {                       
                                                 st.add(s);                       
                                                 // Traverse current string, one by one                       
                                                 // remove every character and recur.                       
                                                 for                                     (let i = 0; i < s.length; i++) {                       
                                                 let t = s;                       
                                                 t = t.substr(0, i) + t.substr(i + 1);                       
                                                 st = generate(st, t);                       
                                                 }                       
                                                 }                       
                                                 return                                     st;                       
                         }                       
           
                         // Driver code                       
                         let s =                                     "xyz"                                     ;                       
           
                         let st =                                     new                                     Set();                       
                         st = generate(st, s);                       
           
                         let str =                                     ''                                     ;                       
                         console.log(st)                       
                         for                                     (item of st.values())                       
                                                 str += item +                                     '<br> '                       
                                   
                         document.write(str);                       
           
                         </script>                       

输出：

xxyxyzxzyyzz

本文由 SANDEEP GAUR MNNIT .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用写极客。组织或者把你的文章寄到contribute@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章