打印数组A[]中的所有字符串，并将数组B[]中的所有字符串作为子序列 _字符串

本文概述

C ++
Java
Python3
C#

给定两个由字符串组成的数组A[]和B[]，任务是将数组A[]中的所有字符串作为子序列输出。
例子：

【打印数组A[]中的所有字符串，并将数组B[]中的所有字符串作为子序列】输入：A [] = {"geeksforgeeks", "mapple", "twitter", "table", "Linkedin"}, B [] = {"e", "l"}
输出：mapple tablelinkedin
说明：两者字符串"e"和"l"是"mapple", "table", "linkedin"中的子集。
输入：A [] = {"geeksforgeeks", "topcoder", "leetcode"}, B [] = {"geek", "ee"}
输出：geeksforgeeks
说明：B [], {"geek", "ee"}仅出现在"geeksforgeeks"中。

简单的方法：
解决这个问题最简单的方法是遍历数组A[]，对于每个字符串，检查数组B[]中的所有字符串是否作为子序列存在。
时间复杂度：O(N^2 * L)，其中length表示数组a[]中字符串的最大长度
辅助空间：O(1)
高效方法：
要优化上述方法, 请按照以下步骤操作：
初始化矩阵A_fre[][]，其中A_fre[i]存储第i个字符串中每个字符的频率。
初始化B_fre[]来存储数组B[]中所有字符的频率。
遍历数组A[]，对于每个字符串，检查一个字符在数组B[]中的字符串中是否比在A[]中的ith字符串中有更多的频率，即。

如果A_fre [i] [j] < B_fre [j], 其中A_fre [i] [j]：A []中第i个字符串中具有ASCII值('a'+ j)的字符的频率。 B_fre [j]：B []字符串中具有ASCII值('a'+ j)的字符的频率。

那么该字符串中至少有一个字符串B []这不是它的子序列。
如果上述条件不满足A[]中的任何字符串的所有字符，则输出该字符串作为一个答案。
检查A[]中的所有字符串后，如果没有发现有B[]中的所有字符串作为其固有子集，则打印-1。
下面是上述方法的实现：
C ++

// C++ Program to implement the // above approach #include < bits/stdc++.h> using namespace std; // Function to find strings from A[] // having all strings in B[] as subsequence void UniversalSubset(vector< string> A, vector< string> B) { // Calculate respective sizes int n1 = A.size(); int n2 = B.size(); // Stores the answer vector< string> res; // Stores the frequency of each // character in strings of A[] int A_fre[n1][26]; for ( int i = 0; i < n1; i++) { for ( int j = 0; j < 26; j++) A_fre[i][j] = 0; }// Compute the frequencies // of characters of all strings for ( int i = 0; i < n1; i++) { for ( int j = 0; j < A[i].size(); j++) { A_fre[i][A[i][j] - 'a' ]++; } }// Stores the frequency of each // character in strings of B[] // each character of a string in B[] int B_fre[26] = { 0 }; for ( int i = 0; i < n2; i++) { int arr[26] = { 0 }; for ( int j = 0; j < B[i].size(); j++) {arr[B[i][j] - 'a' ]++; B_fre[B[i][j] - 'a' ] = max(B_fre[B[i][j] - 'a' ], arr[B[i][j] - 'a' ]); } }for ( int i = 0; i < n1; i++) { int flag = 0; for ( int j = 0; j < 26; j++) {// If the frequency of a character // in B[] exceeds that in A[] if (A_fre[i][j] < B_fre[j]) {// A string exists in B[] which // is not a proper subset of A[i] flag = 1; break ; } }// If all strings in B[] are // proper subset of A[] if (flag == 0) // Push the string in // resultant vector res.push_back(A[i]); }// If any string is found if (res.size()) {// Print those strings for ( int i = 0; i < res.size(); i++) { for ( int j = 0; j < res[i].size(); j++) cout < < res[i][j]; }cout < < " " ; }// Otherwise else cout < < "-1" ; }// Driver code int main() { vector< string> A = { "geeksforgeeks" , "topcoder" , "leetcode" }; vector< string> B = { "geek" , "ee" }; UniversalSubset(A, B); return 0; }

Java

// Java program to implement // the above approach import java.util.*; class GFG {// Function to find strings from A[] // having all strings in B[] as subsequence static void UniversalSubset(List< String> A, List< String> B) { // Calculate respective sizes int n1 = A.size(); int n2 = B.size(); // Stores the answer List< String> res = new ArrayList< > (); // Stores the frequency of each // character in strings of A[] int [][] A_fre = new int [n1][ 26 ]; for ( int i = 0 ; i < n1; i++) { for ( int j = 0 ; j < 26 ; j++) A_fre[i][j] = 0 ; } // Compute the frequencies // of characters of all strings for ( int i = 0 ; i < n1; i++) { for ( int j = 0 ; j < A.get(i).length(); j++) { A_fre[i][A.get(i).charAt(j) - 'a' ]++; } } // Stores the frequency of each // character in strings of B[] // each character of a string in B[] int [] B_fre = new int [ 26 ]; for ( int i = 0 ; i < n2; i++) { int [] arr = new int [ 26 ] ; for ( int j = 0 ; j < B.get(i).length(); j++) { arr[B.get(i).charAt(j) - 'a' ]++; B_fre[B.get(i).charAt(j) - 'a' ] = Math.max( B_fre[B.get(i).charAt(j) - 'a' ], arr[B.get(i).charAt(j) - 'a' ]); } } for ( int i = 0 ; i < n1; i++) { int flag = 0 ; for ( int j = 0 ; j < 26 ; j++) { // If the frequency of a character // in B[] exceeds that in A[] if (A_fre[i][j] < B_fre[j]) { // A string exists in B[] which // is not a proper subset of A[i] flag = 1 ; break ; } } // If all strings in B[] are // proper subset of A[] if (flag == 0 ) // Push the string in // resultant vector res.add(A.get(i)); } // If any string is found if (res.size() != 0 ) { // Print those strings for ( int i = 0 ; i < res.size(); i++) { for ( int j = 0 ; j < res.get(i).length(); j++) System.out.print(res.get(i).charAt(j)); } System.out.print( " " ); } // Otherwise else System.out.print( "-1" ); }// Driver code public static void main (String[] args) { List< String> A = Arrays.asList( "geeksforgeeks" , "topcoder" , "leetcode" ); List< String> B = Arrays.asList( "geek" , "ee" ); UniversalSubset(A, B); } }// This code is contributed by offbeat

Python3

# Python3 program to implement # the above approach# Function to find strings from A[] # having all strings in B[] as subsequence def UniversalSubset(A, B):# Calculate respective sizes n1 = len (A) n2 = len (B)# Stores the answer res = []# Stores the frequency of each # character in strings of A[] A_freq = [[ 0 for x in range ( 26 )] for y in range (n1)]# Compute the frequencies # of characters of all strings for i in range (n1): for j in range ( len (A[i])): A_freq[i][ ord (A[i][j]) - ord ( 'a' )] + = 1# Stores the frequency of each # character in strings of B[] # each character of a string in B[] B_freq = [ 0 ] * 26for i in range (n2): arr = [ 0 ] * 26for j in range ( len (B[i])): arr[ ord (B[i][j]) - ord ( 'a' )] + = 1B_freq[ ord (B[i][j]) - ord ( 'a' )] = max ( B_freq[ ord (B[i][j]) - ord ( 'a' )], arr[ ord (B[i][j]) - ord ( 'a' )])for i in range (n1): flag = 0 for j in range ( 26 ):# If the frequency of a character # in B[] exceeds that in A[] if (A_freq[i][j] < B_freq[j]):# A string exists in B[] which # is not a proper subset of A[i] flag = 1 break# If all strings in B[] are # proper subset of A[] if (flag = = 0 ):# Push the string in # resultant vector res.append(A[i])# If any string is found if ( len (res)):# Print those strings for i in range ( len (res)): for j in range ( len (res[i])): print (res[i][j], end = "")# Otherwise else : print ( - 1 , end = "")# Driver code if __name__ = = '__main__' :A = [ "geeksforgeeks" , "topcoder" , "leetcode" ] B = [ "geek" , "ee" ]UniversalSubset(A, B)# This code is contributed by Shivam Singh

// C# program to implement // the above approach using System; using System.Collections.Generic; class GFG{// Function to find strings from []A // having all strings in []B as subsequence static void UniversalSubset(List< String> A, List< String> B) {// Calculate respective sizes int n1 = A.Count; int n2 = B.Count; // Stores the answer List< String> res = new List< String> (); // Stores the frequency of each // character in strings of []A int [, ] A_fre = new int [n1, 26]; for ( int i = 0; i < n1; i++) { for ( int j = 0; j < 26; j++) A_fre[i, j] = 0; }// Compute the frequencies // of characters of all strings for ( int i = 0; i < n1; i++) { for ( int j = 0; j < A[i].Length; j++) { A_fre[i, A[i][j] - 'a' ]++; } }// Stores the frequency of each // character in strings of []B // each character of a string in []B int [] B_fre = new int [26]; for ( int i = 0; i < n2; i++) { int [] arr = new int [26]; for ( int j = 0; j < B[i].Length; j++) { arr[B[i][j] - 'a' ]++; B_fre[B[i][j] - 'a' ] = Math.Max( B_fre[B[i][j] - 'a' ], arr[B[i][j] - 'a' ]); } }for ( int i = 0; i < n1; i++) { int flag = 0; for ( int j = 0; j < 26; j++) {// If the frequency of a character // in []B exceeds that in []A if (A_fre[i, j] < B_fre[j]) {// A string exists in []B which // is not a proper subset of A[i] flag = 1; break ; } }// If all strings in []B are // proper subset of []A if (flag == 0)// Push the string in // resultant vector res.Add(A[i]); }// If any string is found if (res.Count != 0) {// Print those strings for ( int i = 0; i < res.Count; i++) { for ( int j = 0; j < res[i].Length; j++) Console.Write(res[i][j]); } Console.Write( " " ); }// Otherwise else Console.Write( "-1" ); }// Driver code public static void Main(String[] args) { List< String> A = new List< String> (); A.Add( "geeksforgeeks" ); A.Add( "topcoder" ); A.Add( "leetcode" ); List< String> B = new List< String> (); B.Add( "geek" ); B.Add( "ee" ); UniversalSubset(A, B); } }// This code is contributed by amal kumar choubey

输出如下：