Dado un conjunto de strings de la misma longitud, necesitamos encontrar la longitud de la string más larga, que es una string de prefijo de al menos dos strings.
Ejemplos:
Input: ["abcde", "abcsd", "bcsdf", "abcda", "abced"] Output: 4 Explanation: Longest prefix string is "abcd". Input: ["pqrstq", "pwxyza", "abcdef", "pqrstu"] Output: 5
Acercarse:
- Comenzando desde la posición 0, itere sobre cada carácter y verifique si ese carácter aparece en al menos dos de las strings en la posición actual o no.
- Si ocurre, llama recursivamente a la siguiente posición. De lo contrario,
- Actualice el valor máximo tomando el máximo actual con Current_position – 1.
- Finalmente, devuelva el valor máximo.
C++
// C++ program to find longest // string which is prefix string // of at least two strings #include<bits/stdc++.h> using namespace std; int max1=0; // Function to find Max length // of the prefix int MaxLength(vector<string> v, int i, int m) { // Base case if(i>=m) { return m-1; } // Iterating over all the alphabets for(int k = 0; k < 26; k++) { char c = 'a' + k; vector<string> v1; // Checking if char exists in // current string or not for(int j = 0; j < v.size(); j++) { if(v[j][i] == c) { v1.push_back(v[j]); } } // If atleast 2 string have // that character if(v1.size()>=2) { // Recursive call to i+1 max1=max(max1, MaxLength(v1, i+1, m)); } else { max1=max(max1, i - 1); } } return max1; } // Driver code int main() { // Initialising strings string s1, s2, s3, s4, s5; s1 = "abcde"; s2 = "abcsd"; s3 = "bcsdf"; s4 = "abcda"; s5 = "abced"; vector<string> v; // push strings into vectors. v.push_back(s1); v.push_back(s2); v.push_back(s3); v.push_back(s4); v.push_back(s5); int m = v[0].size(); cout<<MaxLength(v, 0, m) + 1<<endl; return 0; }
Java
// Java program to find longest // String which is prefix String // of at least two Strings import java.util.*; class GFG{ static int max1 = 0; // Function to find Max length // of the prefix static int MaxLength(Vector<String> v, int i, int m) { // Base case if(i>=m) { return m-1; } // Iterating over all the alphabets for(int k = 0; k < 26; k++) { char c = (char)('a' + k); Vector<String> v1 = new Vector<String>(); // Checking if char exists in // current String or not for(int j = 0; j < v.size(); j++) { if(v.get(j).charAt(i) == c) { v1.add(v.get(j)); } } // If atleast 2 String have // that character if(v1.size() >= 2) { // Recursive call to i+1 max1=Math.max(max1, MaxLength(v1, i + 1, m)); } else { max1=Math.max(max1, i - 1); } } return max1; } // Driver code public static void main(String[] args) { // Initialising Strings String s1, s2, s3, s4, s5; s1 = "abcde"; s2 = "abcsd"; s3 = "bcsdf"; s4 = "abcda"; s5 = "abced"; Vector<String> v = new Vector<String>(); // push Strings into vectors. v.add(s1); v.add(s2); v.add(s3); v.add(s4); v.add(s5); int m = v.get(0).length(); System.out.print(MaxLength(v, 0, m) + 1); } } // This code is contributed by shikhasingrajput
Python3
# Python3 program to find longest # string which is prefix string # of at least two strings max1 = 0 # Function to find max length # of the prefix def MaxLength(v, i, m): global max1 # Base case if(i >= m): return m - 1 # Iterating over all the alphabets for k in range(26): c = chr(ord('a') + k) v1 = [] # Checking if char exists in # current string or not for j in range(len(v)): if(v[j][i] == c): v1.append(v[j]) # If atleast 2 string have # that character if(len(v1) >= 2): # Recursive call to i+1 max1 = max(max1, MaxLength(v1, i + 1, m)) else: max1 = max(max1, i - 1) return max1 # Driver code if __name__ == '__main__': # Initialising strings s1 = "abcde" s2 = "abcsd" s3 = "bcsdf" s4 = "abcda" s5 = "abced" v = [] # Push strings into vectors. v.append(s1) v.append(s2) v.append(s3) v.append(s4) v.append(s5) m = len(v[0]) print(MaxLength(v, 0, m) + 1) # This code is contributed by BhupendraSingh
C#
// C# program to find longest // String which is prefix String // of at least two Strings using System; using System.Collections.Generic; class GFG{ static int max1 = 0; // Function to find Max length // of the prefix static int MaxLength(List<String> v, int i, int m) { // Base case if (i >= m) { return m - 1; } // Iterating over all the alphabets for(int k = 0; k < 26; k++) { char c = (char)('a' + k); List<String> v1 = new List<String>(); // Checking if char exists in // current String or not for(int j = 0; j < v.Count; j++) { if (v[j][i] == c) { v1.Add(v[j]); } } // If atleast 2 String have // that character if (v1.Count >= 2) { // Recursive call to i+1 max1 = Math.Max(max1, MaxLength(v1, i + 1, m)); } else { max1 = Math.Max(max1, i - 1); } } return max1; } // Driver code public static void Main(String[] args) { // Initialising Strings String s1, s2, s3, s4, s5; s1 = "abcde"; s2 = "abcsd"; s3 = "bcsdf"; s4 = "abcda"; s5 = "abced"; List<String> v = new List<String>(); // push Strings into vectors. v.Add(s1); v.Add(s2); v.Add(s3); v.Add(s4); v.Add(s5); int m = v[0].Length; Console.Write(MaxLength(v, 0, m) + 1); } } // This code is contributed by Amit Katiyar
Javascript
<script> // Javascript program to find longest // string which is prefix string // of at least two strings let max1=0; // Function to find Max length // of the prefix function MaxLength(v, i, m) { // Base case if(i>=m) { return m-1; } // Iterating over all the alphabets for(let k = 0; k < 26; k++) { let c = String.fromCharCode('a'.charCodeAt(0) + k); let v1 = []; // Checking if char exists in // current string or not for(let j = 0; j < v.length; j++) { if(v[j][i] == c) { v1.push(v[j]); } } // If atleast 2 string have // that character if(v1.length >= 2) { // Recursive call to i+1 max1 = Math.max(max1, MaxLength(v1, i+1, m)); } else { max1 = Math.max(max1, i - 1); } } return max1; } // Driver code // Initialising strings let s1, s2, s3, s4, s5; s1 = "abcde"; s2 = "abcsd"; s3 = "bcsdf"; s4 = "abcda"; s5 = "abced"; let v = []; // push strings into vectors. v.push(s1); v.push(s2); v.push(s3); v.push(s4); v.push(s5); let m = v[0].length; document.write(MaxLength(v, 0, m) + 1 + "<br>"); </script>
Producción:
4
Publicación traducida automáticamente
Artículo escrito por jay_umiya_mata y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA