String más larga que es una string de prefijo de al menos dos strings

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

Deja una respuesta

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