Dada una array de strings arr[] , la tarea es encontrar la longitud del prefijo común más largo reorganizando los caracteres de cada string de la array dada.
Ejemplos:
Entrada: arr[] = {“aabdc”, “abcd”, “aacd”}
Salida: 3
Explicación: Reorganiza los caracteres de cada string de la array dada de modo que la array se convierta en {“acdab”, “acdb”, “acda” }.
Por lo tanto, el prefijo común más largo de todas las strings de la array dada es «acd» que tiene una longitud igual a 3.Entrada: arr[] = {“abcdef”, “adgfse”, “fhfdd”}
Salida: 2
Explicación: Reorganiza los caracteres de cada string de la array dada de modo que la array se convierta en {“dfcaeb”, “dfgase”, “dffhd” }.
Por lo tanto, el prefijo común más largo de todas las strings de la array dada es «df» que tiene una longitud igual a 2.
Enfoque ingenuo: el enfoque más simple para resolver este problema es generar todas las permutaciones posibles de cada string de la array dada y encontrar el prefijo común más largo de todas las strings . Finalmente, imprima la longitud del prefijo común más largo.
Complejidad de tiempo: O(N * log M * (M!) N )
Espacio auxiliar: O(M), N es el número de strings, M es la longitud de la string más larga.
Enfoque eficiente: para optimizar el enfoque anterior, la idea es utilizar Hashing . Siga los pasos a continuación para resolver el problema:
- Inicialice una array 2D , digamos freq[N][256] tal que freq[i][j] almacene la frecuencia de un carácter (= j) en la string arr[i] .
- Recorre la array dada y almacena la frecuencia de arr[i][j] en freq[i][arr[i][j]] .
- Inicialice una variable, digamos maxLen para almacenar la longitud del prefijo común más largo
- Itere sobre todos los caracteres posibles y encuentre la frecuencia mínima, diga minRowVal del carácter actual en todas las strings de la array dada, e incremente el valor de maxLen por minRowVal
- Finalmente, imprima el valor de maxLen .
A continuación se muestra la implementación del enfoque anterior:
C++14
// C++ program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to get the length
// of the longest common prefix
// by rearranging the strings
int longComPre(string arr[], int N)
{
// freq[i][j]: stores the frequency
// of a character(= j) in
// a string arr[i]
int freq[N][256];
// Initialize freq[][] array.
memset(freq, 0, sizeof(freq));
// Traverse the given array
for (int i = 0; i < N; i++) {
// Stores length of
// current string
int M = arr[i].length();
// Traverse current string
// of the given array
for (int j = 0; j < M;
j++) {
// Update the value of
// freq[i][arr[i][j]]
freq[i][arr[i][j]]++;
}
}
// Stores the length of
// longest common prefix
int maxLen = 0;
// Count the minimum frequency
// of each character in
// in all the strings of arr[]
for (int j = 0; j < 256; j++) {
// Stores minimum value
// in each row of freq[][]
int minRowVal = INT_MAX;
// Calculate minimum frequency
// of current character
// in all the strings.
for (int i = 0; i < N;
i++) {
// Update minRowVal
minRowVal = min(minRowVal,
freq[i][j]);
}
// Update maxLen
maxLen += minRowVal;
}
return maxLen;
}
// Driver Code
int main()
{
string arr[] = { "aabdc",
"abcd",
"aacd" };
int N = 3;
cout << longComPre(arr, N);
}
Java
// Java program to implement
// the above approach
import java.util.*;
class GFG{
// Function to get the length
// of the longest common prefix
// by rearranging the Strings
static int longComPre(String arr[],
int N)
{
// freq[i][j]: stores the
// frequency of a character(= j)
// in a String arr[i]
int [][]freq = new int[N][256];
// Traverse the given array
for (int i = 0; i < N; i++)
{
// Stores length of
// current String
int M = arr[i].length();
// Traverse current String
// of the given array
for (int j = 0; j < M; j++)
{
// Update the value of
// freq[i][arr[i][j]]
freq[i][arr[i].charAt(j)]++;
}
}
// Stores the length of
// longest common prefix
int maxLen = 0;
// Count the minimum frequency
// of each character in
// in all the Strings of arr[]
for (int j = 0; j < 256; j++)
{
// Stores minimum value
// in each row of freq[][]
int minRowVal = Integer.MAX_VALUE;
// Calculate minimum frequency
// of current character
// in all the Strings.
for (int i = 0; i < N; i++)
{
// Update minRowVal
minRowVal = Math.min(minRowVal,
freq[i][j]);
}
// Update maxLen
maxLen += minRowVal;
}
return maxLen;
}
// Driver Code
public static void main(String[] args)
{
String arr[] = {"aabdc",
"abcd",
"aacd"};
int N = 3;
System.out.print(longComPre(arr, N));
}
}
// This code is contributed by gauravrajput1
Python3
# Python3 program to implement # the above approach import sys # Function to get the length # of the longest common prefix # by rearranging the strings def longComPre(arr, N): # freq[i][j]: stores the frequency # of a character(= j) in # a arr[i] freq = [[0 for i in range(256)] for i in range(N)] # Initialize freq[][] array. # memset(freq, 0, sizeof(freq)) # Traverse the given array for i in range(N): # Stores length of # current string M = len(arr[i]) # Traverse current string # of the given array for j in range(M): # Update the value of # freq[i][arr[i][j]] freq[i][ord(arr[i][j])] += 1 # Stores the length of # longest common prefix maxLen = 0 # Count the minimum frequency # of each character in #in all the strings of arr[] for j in range(256): # Stores minimum value # in each row of freq[][] minRowVal = sys.maxsize # Calculate minimum frequency # of current character # in all the strings. for i in range(N): # Update minRowVal minRowVal = min(minRowVal, freq[i][j]) # Update maxLen maxLen += minRowVal return maxLen # Driver Code if __name__ == '__main__': arr = [ "aabdc", "abcd", "aacd" ] N = 3 print(longComPre(arr, N)) # This code is contributed by mohit kumar 29
C#
// C# program to implement
// the above approach
using System;
class GFG{
// Function to get the length
// of the longest common prefix
// by rearranging the Strings
static int longComPre(String []arr,
int N)
{
// freq[i,j]: stores the
// frequency of a character(= j)
// in a String arr[i]
int [,]freq = new int[N, 256];
// Traverse the given array
for (int i = 0; i < N; i++)
{
// Stores length of
// current String
int M = arr[i].Length;
// Traverse current String
// of the given array
for (int j = 0; j < M; j++)
{
// Update the value of
// freq[i,arr[i,j]]
freq[i, arr[i][j]]++;
}
}
// Stores the length of
// longest common prefix
int maxLen = 0;
// Count the minimum frequency
// of each character in
// in all the Strings of []arr
for (int j = 0; j < 256; j++)
{
// Stores minimum value
// in each row of [,]freq
int minRowVal = int.MaxValue;
// Calculate minimum frequency
// of current character
// in all the Strings.
for (int i = 0; i < N; i++)
{
// Update minRowVal
minRowVal = Math.Min(minRowVal,
freq[i, j]);
}
// Update maxLen
maxLen += minRowVal;
}
return maxLen;
}
// Driver Code
public static void Main(String[] args)
{
String []arr = {"aabdc",
"abcd",
"aacd"};
int N = 3;
Console.Write(longComPre(arr, N));
}
}
// This code is contributed by gauravrajput1
Javascript
<script>
// Javascript program to implement
// the above approach
// Function to get the length
// of the longest common prefix
// by rearranging the Strings
function longComPre(arr, N)
{
// freq[i][j]: stores the
// frequency of a character(= j)
// in a String arr[i]
let freq = new Array(N);
for(let i = 0; i < N; i++)
{
freq[i] = new Array(256);
for(let j = 0; j < 256; j++)
{
freq[i][j] = 0;
}
}
// Traverse the given array
for (let i = 0; i < N; i++)
{
// Stores length of
// current String
let M = arr[i].length;
// Traverse current String
// of the given array
for (let j = 0; j < M; j++)
{
// Update the value of
// freq[i][arr[i][j]]
freq[i][arr[i][j].charCodeAt(0)]++;
}
}
// Stores the length of
// longest common prefix
let maxLen = 0;
// Count the minimum frequency
// of each character in
// in all the Strings of arr[]
for (let j = 0; j < 256; j++)
{
// Stores minimum value
// in each row of freq[][]
let minRowVal = Number.MAX_VALUE;
// Calculate minimum frequency
// of current character
// in all the Strings.
for (let i = 0; i < N; i++)
{
// Update minRowVal
minRowVal = Math.min(minRowVal,
freq[i][j]);
}
// Update maxLen
maxLen += minRowVal;
}
return maxLen;
}
// Driver Code
let arr= ["aabdc",
"abcd",
"aacd"];
let N = 3;
document.write(longComPre(arr, N));
// This code is contributed by patel2127
</script>
Producción
3
Complejidad de Tiempo: O(N * (M + 256))
Espacio Auxiliar: O(N * 256)
Publicación traducida automáticamente
Artículo escrito por costheta_z y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA