原文：
给定两个由字符串组成的数组a[]和b[]，任务是从数组a[]中打印所有字符串都位于b[]作为子序列。
示例：
输入：
a[] = {"geeksforgeeks", "mapple", "twitter", "table", "linkedin"}, b [] = {"e", "l"}输出：
maplet 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[]中的字符串i的频率更高。如果
a_fre[i][j] < b_fre[j]，其中：a_fre[i][j]：a[i]中 ascii 值为（'a' j）的字符的频率。b_fre[i][j]：b[i]中 ascii 值为（'a' j）的字符的频率。那么该字符串在
b[]中至少有一个字符串，而不是其子序列。 -
如果
a[]中的任何字符串的所有字符都不满足上述条件，请将该字符串打印为答案。 -
在检查了
a[]中的所有字符串后，如果没有发现将b[]中的所有字符串作为其适当子集的字符串，请打印-1。
下面是上述方法的实现：
c
// c program to implement the
// above approach
#include
using namespace std;
// function to find strings from a[]
// having all strings in b[] as subsequence
void universalsubset(vector a,
vector b)
{
// calculate respective sizes
int n1 = a.size();
int n2 = b.size();
// stores the answer
vector 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 a = { "geeksforgeeks",
"topcoder",
"leetcode" };
vector 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 a,
list b)
{
// calculate respective sizes
int n1 = a.size();
int n2 = b.size();
// stores the answer
list 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 a = arrays.aslist("geeksforgeeks",
"topcoder",
"leetcode");
list 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] * 26
for i in range(n2):
arr = [0] * 26
for j in range(len(b[i])):
arr[ord(b[i][j]) - ord('a')] = 1
b_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
// 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 a,
list b)
{
// calculate respective sizes
int n1 = a.count;
int n2 = b.count;
// stores the answer
list res = new list();
// 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 a = new list();
a.add("geeksforgeeks");
a.add("topcoder");
a.add("leetcode");
list b = new list();
b.add("geek");
b.add("ee");
universalsubset(a, b);
}
}
// this code is contributed by amal kumar choubey
输出：
geeksforgeeks
时间复杂度：o(n * l)，其中length表示数组a[]中字符串的最大长度。
辅助空间：o(n)。
麻将胡了pg电子网站的版权属于：月萌api www.moonapi.com，转载请注明出处
