如何使用ArrayList打印字符串的所有子序列?

2021年3月27日13:44:19 发表评论 745 次浏览

本文概述

给定一个字符串str,任务是打印str的所有子序列。

子序列是指可以通过删除一些或不删除元素而不改变其余元素顺序的方法从另一个序列派生出来的序列。

例子:

输入:str =" abc"
输出:a b a b c ac bc abc
输入:str =" geek"
输出:g ge e ge ee gee k gk ek gek ek gek eek geek

方法:编写一个递归函数,将字符串str[0]的第一个字符追加到每个子序列的开头,然后输出从第二个字符str[1, n - 1]开始的子字符串的每个子序列。终止条件将是当传递的字符串为空时,在这种情况下,函数将返回一个空数组列表。

下面是上述方法的实现:

Java

// Java implementation of the approach
import java.util.ArrayList;
 
public class GFG {
 
     // Utility function to print the contents
     // of the ArrayList
     static void printArrayList(ArrayList<String> arrL)
     {
         arrL.remove( "" );
         for ( int i = 0 ; i < arrL.size(); i++)
             System.out.print(arrL.get(i) + " " );
     }
 
     // Function to returns the arraylist which contains
     // all the sub-sequences of str
     public static ArrayList<String> getSequence(String str)
     {
 
         // If string is empty
         if (str.length() == 0 ) {
 
             // Return an empty arraylist
             ArrayList<String> empty = new ArrayList<>();
             empty.add( "" );
             return empty;
         }
 
         // Take first character of str
         char ch = str.charAt( 0 );
 
         // Take sub-string starting from the
         // second character
         String subStr = str.substring( 1 );
 
         // Recurvise call for all the sub-sequences
         // starting from the second character
         ArrayList<String> subSequences =
                               getSequence(subStr);
 
         // Add first character from str in the beginning
         // of every character from the sub-sequences
         // and then store it into the resultant arraylist
         ArrayList<String> res = new ArrayList<>();
         for (String val : subSequences) {
             res.add(val);
             res.add(ch + val);
         }
 
         // Return the resultant arraylist
         return res;
     }
 
     // Driver code
     public static void main(String[] args)
     {
         String str = "geek" ;
         printArrayList(getSequence(str));
         // System.out.print(getSequence(str));
     }
}

C#

// C# implementation of the approach
using System;
using System.Collections.Generic;
 
class GFG{
 
     // Utility function to print the contents
     // of the List
     static void printList(List<String> arrL)
     {
         arrL.Remove( "" );
         for ( int i = 0; i < arrL.Count; i++)
             Console.Write(arrL[i] + " " );
     }
 
     // Function to returns the arraylist which contains
     // all the sub-sequences of str
     public static List<String> getSequence(String str)
     {
 
         // If string is empty
         if (str.Length == 0)
         {
 
             // Return an empty arraylist
             List<String> empty = new List<String>();
             empty.Add( "" );
             return empty;
         }
 
         // Take first character of str
         char ch = str[0];
 
         // Take sub-string starting from the
         // second character
         String subStr = str.Substring(1);
 
         // Recurvise call for all the sub-sequences
         // starting from the second character
         List<String> subSequences = getSequence(subStr);
 
         // Add first character from str in the beginning
         // of every character from the sub-sequences
         // and then store it into the resultant arraylist
         List<String> res = new List<String>();
         foreach (String val in subSequences)
         {
             res.Add(val);
             res.Add(ch + val);
         }
 
         // Return the resultant arraylist
         return res;
     }
 
     // Driver code
     public static void Main(String[] args)
     {
         String str = "geek" ;
         printList(getSequence(str));
         // Console.Write(getSequence(str));
     }
}
 
// This code is contributed by Rohit_ranjan

输出如下:

g e ge e ge ee gee k gk ek gek ek gek eek geek

替代解决方案:

一对一地修复字符, 并从它们开始递归地生成所有子集。

Java

// Java implementation of the approach
public class sub_sequence {
 
     // Function to print all the sub-sequences
     // of a string
     public static void printSubSeq(String sub, String ans)
     {
 
         if (sub.length() == 0 ) {
             System.out.print( "" + ans + " " );
             return ;
         }
 
         // First character of sub
         char ch = sub.charAt( 0 );
 
         // Sub-string starting from second
         // character of sub
         String ros = sub.substring( 1 );
 
         // Excluding first character
         printSubSeq(ros, ans);
 
         // Including first character
         printSubSeq(ros, ans + ch);
     }
 
     // Driver code
     public static void main(String[] args)
     {
         String str = "abc" ;
         printSubSeq(str, "" );
     }
}

C#

// C# implementation of the approach
using System;
 
class GFG
{
 
// Function to print all the 
// sub-sequences of a string
public static void printSubSeq( string sub, string ans)
{
     if (sub.Length == 0)
     {
         Console.Write( "" + ans + " " );
         return ;
     }
 
     // First character of sub
     char ch = sub[0];
 
     // Sub-string starting from second
     // character of sub
     string ros = sub.Substring(1);
 
     // Excluding first character
     printSubSeq(ros, ans);
 
     // Including first character
     printSubSeq(ros, ans + ch);
}
 
// Driver code
public static void Main()
{
     string str = "abc" ;
     printSubSeq(str, "" ) ;
}
}
 
// This code is contributed by Ryuga

输出如下:

c b bc a ac ab abc

木子山

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: