Recuento de superstrings en una array dada de strings

Dadas 2 arrays de strings X e Y , la tarea es encontrar el número de superstrings en X.

Se dice que una string s es una Superstring, si cada string presente en el arreglo Y es una subsecuencia de la string s  .

Ejemplos:

Entrada : X = {“ceo”, “alco”, “caaeio”, “ceai”}, Y = {“ec”, “oc”, “ceo”}
Salida : 2
Explicación : Strings “ceo” y “caaeio” son superstrings ya que cada string de la array Y es un subconjunto de estas 2 strings. No se incluyen otras strings en la respuesta; todas las strings de la array Y no son 
subconjuntos de ellas.

Entrada : X = {“iopo”, “oaai”, “iipo”}, Y = {“oo”}
Salida : 1

 

Enfoque: La idea es usar el concepto de Hashing para almacenar las frecuencias de los caracteres para resolver el problema. Siga los pasos a continuación para resolver el problema:

  • Inicialice una array de tamaño 26 para almacenar el máximo de ocurrencias de cada carácter[az] en cada string presente en la array Y .
  • Ahora considere cada string s en X,
    • Compruebe si la frecuencia de cada carácter en s es mayor que igual a la frecuencia obtenida del paso anterior

A continuación se muestra la implementación del enfoque anterior:

C++

// C++ implementation for the above approach
 
#include <iostream>
using namespace std;
 
// Function to find total number of superstrings
int superstring(string X[], string Y[], int N, int M)
{
 
    // Array to store max frequency
    // Of each letter
    int maxFreq[26];
    for (int i = 0; i < 26; i++)
        maxFreq[i] = 0;
 
    for (int j = 0; j < M; j++) {
        int temp[26];
        for (int i = 0; i < 26; i++)
            temp[i] = 0;
        for (int k = 0; k < Y[j].size(); k++) {
            temp[Y[j][k] - 'a']++;
        }
        for (int i = 0; i < 26; i++) {
            maxFreq[i] = max(maxFreq[i], temp[i]);
        }
    }
 
    int ans = 0;
    for (int j = 0; j < N; j++) {
 
        // Array to find frequency of each letter in string
        // x
        int temp[26];
        for (int i = 0; i < 26; i++)
            temp[i] = 0;
        for (int k = 0; k < X[j].size(); k++) {
            temp[X[j][k] - 'a']++;
        }
        int i = 0;
        for (i = 0; i < 26; i++) {
 
            // If any frequency is less in string x than
            // maxFreq, then it can't be a superstring
            if (temp[i] < maxFreq[i]) {
                break;
            }
        }
        if (i == 26) {
 
            // Increment counter of x is a superstring
            ans++;
        }
    }
    return ans;
}
 
// Driver code
int main()
{
    // Size of array X
    int N = 4;
    // Size of array Y
    int M = 3;
 
    string X[N] = { "ceo", "alco", "caaeio", "ceai" };
    string Y[M] = { "ec", "oc", "ceo" };
 
    cout << superstring(X, Y, N, M); // Function call
    return 0;
}

Java

// Java implementation for the above approach
 
import java.io.*;
 
class GFG {
 
    // Function to find total number of superstrings
    public static int superString(String X[], String Y[],
                                  int N, int M)
    {
 
        // Array to store max frequency
        // Of each letter
        int[] maxFreq = new int[26];
        for (int i = 0; i < 26; i++)
            maxFreq[i] = 0;
 
        for (int j = 0; j < M; j++) {
            int[] temp = new int[26];
            for (int k = 0; k < Y[j].length(); k++) {
                temp[Y[j].charAt(k) - 'a']++;
            }
            for (int i = 0; i < 26; i++) {
                maxFreq[i] = Math.max(maxFreq[i], temp[i]);
            }
        }
 
        int ans = 0;
        for (int j = 0; j < N; j++) {
 
            // Array to find frequency of each letter in
            // string x
            int[] temp = new int[26];
            for (int i = 0; i < 26; i++)
                temp[i] = 0;
            for (int k = 0; k < X[j].length(); k++) {
                temp[X[j].charAt(k) - 'a']++;
            }
 
            int i = 0;
            for (i = 0; i < 26; i++) {
 
                // If any frequency is less in string x than
                // maxFreq, then it can't be a superstring
                if (temp[i] < maxFreq[i]) {
                    break;
                }
            }
            if (i == 26) {
 
                // Increment counter of x is a superstring
                ans++;
            }
        }
        return ans;
    }
 
    // Driver code
    public static void main(String[] args)
    {
        String[] X = new String[] { "ceo", "alco", "caaeio",
                                    "ceai" };
        String[] Y = new String[] { "ec", "oc", "ceo" };
 
        System.out.println(
            superString(X, Y, X.length, Y.length));
    }
}

Python3

# Python3 implementation for the above approach
 
# Function to find total number of superstrings
def superstring(X, Y, N, M):
 
    # Array to store max frequency
    # Of each letter
    maxFreq = [0] * 26
 
    for j in range(M):
        temp = [0] * 26
        for k in range(len(Y[j])):
            temp[ord(Y[j][k]) - ord('a')] += 1
        for i in range(26):
            maxFreq[i] = max(maxFreq[i], temp[i])
 
    ans = 0
    for j in range(N):
         
        # Array to find frequency of each letter
        # in string x
        temp = [0] * 26
        for k in range(len(X[j])):
            temp[ord(X[j][k]) - ord('a')] += 1
             
        i = 0
         
        while i < 26:
             
            # If any frequency is less in x than
            # maxFreq, then it can't be a superstring
            if (temp[i] < maxFreq[i]):
                break
            i += 1
        if (i == 26):
             
            # Increment counter of x is a superstring
            ans += 1
 
    return ans
 
# Driver code
if __name__ == '__main__':
     
    # Size of array X
    N = 4
     
    # Size of array Y
    M = 3
 
    X = ["ceo", "alco", "caaeio", "ceai"]
    Y = [ "ec", "oc", "ceo" ]
 
    print(superstring(X, Y, N, M)) #Function call
 
# This code is contributed by mohit kumar 29

C#

// C# program for the above approach
using System;
class GFG
{
 
    // Function to find total number of superstrings
    public static int superString(string[] X, string[] Y,
                                  int N, int M)
    {
 
        // Array to store max frequency
        // Of each letter
        int[] maxFreq = new int[26];
        for (int i = 0; i < 26; i++)
            maxFreq[i] = 0;
 
        for (int j = 0; j < M; j++) {
            int[] temp = new int[26];
            for (int k = 0; k < Y[j].Length; k++) {
                temp[Y[j][k] - 'a']++;
            }
            for (int i = 0; i < 26; i++) {
                maxFreq[i] = Math.Max(maxFreq[i], temp[i]);
            }
        }
 
        int ans = 0;
        for (int j = 0; j < N; j++) {
 
            // Array to find frequency of each letter in
            // string x
            int[] temp = new int[26];
            int i =0;
            for ( i = 0; i < 26; i++)
                temp[i] = 0;
            for (int k = 0; k < X[j].Length; k++) {
                temp[X[j][k] - 'a']++;
            }
 
            for ( i = 0; i < 26; i++) {
 
                // If any frequency is less in string x than
                // maxFreq, then it can't be a superstring
                if (temp[i] < maxFreq[i]) {
                    break;
                }
            }
            if ( i == 26) {
 
                // Increment counter of x is a superstring
                ans++;
            }
        }
        return ans;
    }
 
// Driver code
static void Main()
{
    string[] X = new String[] { "ceo", "alco", "caaeio",
                                    "ceai" };
        string[] Y = new String[] { "ec", "oc", "ceo" };
 
        Console.Write(
            superString(X, Y, X.Length, Y.Length));
}
}
 
// This code is contributed b sanjoy_62.

Javascript

<script>
 
// JavaScript program for the above approach
 
    // Function to find total number of superstrings
    function superString(X, Y, N, M)
    {
 
        // Array to store max frequency
        // Of each letter
        let maxFreq = Array.from({length: 26}, (_, i) => 0);
        for (let i = 0; i < 26; i++)
            maxFreq[i] = 0;
 
        for (let j = 0; j < M; j++) {
            let temp = Array.from({length: 26}, (_, i) => 0);
            for (let k = 0; k < Y[j].length; k++) {
                temp[Y[j][k].charCodeAt() - 'a'.charCodeAt()]++;
            }
            for (let i = 0; i < 26; i++) {
                maxFreq[i] = Math.max(maxFreq[i], temp[i]);
            }
        }
 
        let ans = 0;
        for (let j = 0; j < N; j++) {
 
            // Array to find frequency of each letter in
            // string x
            let temp = Array.from({length: 26}, (_, i) => 0);
            for (let i = 0; i < 26; i++)
                temp[i] = 0;
            for (let k = 0; k < X[j].length; k++) {
                temp[X[j][k].charCodeAt() - 'a'.charCodeAt()]++;
            }
 
            let i = 0;
            for (i = 0; i < 26; i++) {
 
                // If any frequency is less in string x than
                // maxFreq, then it can't be a superstring
                if (temp[i] < maxFreq[i]) {
                    break;
                }
            }
            if (i == 26) {
 
                // Increment counter of x is a superstring
                ans++;
            }
        }
        return ans;
    }
 
    // Driver Code
 
        let X = [ "ceo", "alco", "caaeio",
                                    "ceai" ];
        let Y = [ "ec", "oc", "ceo" ];
 
        document.write(
            superString(X, Y, X.length, Y.length));
 
</script>
Producción: 

2

 

Complejidad del tiempo: O(N*N1 + M*M1), donde N = tamaño de la array X, N1 = longitud máxima (x), M = tamaño de la array Y, M1 = longitud máxima (y),  

Complejidad del espacio: O(1)

Publicación traducida automáticamente

Artículo escrito por RohitOberoi y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *