Najdłuższy wspólny prefiks przy użyciu funkcji Podziel i zwyciężaj

Poziom trudności Ciężko
Często zadawane pytania Accenture Accolita Amazonka Fanatycy Google
Dziel i rządź sznurodwiedzajacy 405

Pytania do rozmowy kwalifikacyjnej na temat projektowania systemu może być tak nieograniczona, że ​​trudno jest określić właściwy sposób przygotowania. Teraz jestem w stanie złamać rundy projektowe Amazon, Microsoft i Adobe po zakupie ta książka. Codziennie poprawiaj jeden pytanie projektowe i obiecuję, że możesz złamać cały projekt.

Problem Statement

W zadaniu „Najdłuższy wspólny prefiks przy użyciu dzielenia i zwyciężania” podaliśmy liczbę całkowitą n i n smyczki. Napisz program, który wydrukuje najdłuższy wspólny prefiks. Jeśli nie ma wspólnego prefiks następnie wypisz „-1”.

Format wejściowy

W pierwszym wierszu znajduje się liczba całkowita n.

Następna linia n zawierająca po jednym ciągu.

Format wyjściowy

Wydrukuj ciąg, który reprezentuje najdłuższy wspólny prefiks podanych ciągów. Jeśli nie znaleziono takiego prefiksu, wypisz „-1”.

ograniczenia

  • 1 <= n <= 10 ^ 3
  • 1 <= | s [i] | <= 10 ^ 3 gdzie i od 0 do n-1
  • s [i] [j] musi być alfabetem angielskim małą literą, gdzie i od 0 do n-1, a j od 0 do | s [i] |.

Przykład

3
tutorial 
tutcup 
turnin
tu

Wyjaśnienie: Tutaj widzimy „tu” to przedrostek występujący w każdym łańcuchu.

Algorytm najdłuższego wspólnego prefiksu przy użyciu funkcji Podziel i zwyciężaj

W tym algorytmie omówiono podejście dziel i rządź. Najpierw dzielimy tablice łańcuchów na dwie części. Następnie robimy to samo dla lewej części, a następnie dla prawej części. Będziemy to robić, dopóki wszystkie łańcuchy nie będą miały długości 1. Teraz zaczniemy podbijać, zwracając wspólny prefiks lewego i prawego łańcucha.

1. Rekurencyjnie podziel tablicę ciągów na dwie części, aż długość wyniesie 1

2. Teraz zacznij podbijać, zwracając wspólny prefiks lewego i prawego łańcucha

Realizacja

Program w C ++ dla najdłuższego wspólnego prefiksu przy użyciu dzielenia i zwyciężania

#include<bits/stdc++.h> 
using namespace std; 

string commonPrefixUtil(string str1, string str2) 
{ 
  string result; 
  int n1 = str1.length(), n2 = str2.length(); 
  for (int i=0,j=0;i<n1&&j<n2;i++,j++) 
  { 
    if(str1[i]!=str2[j]) 
    {
        break; 
    }
    result.push_back(str1[i]); 
  } 
  return result; 
} 

string commonPrefix(string s[], int x, int y) 
{ 
  if(x==y) 
  {
      return s[x]; 
  }
  if(y>x) 
  { 
    int mid=x+(y-x)/2; 
    string s1 = commonPrefix(s, x, mid); 
    string s2 = commonPrefix(s, mid+1, y); 
    return commonPrefixUtil(s1, s2); 
  } 
} 
int main() 
{ 
  int n;
  cin>>n;
  string s[n];
  for(int i=0;i<n;i++)
  {
      cin>>s[i];
  }
  string ans = commonPrefix(s,0,n-1); 
  if(ans.length()>0) 
  {
      cout<<ans<<endl;
  }
  else
  {
    cout<<-1<<endl; 
  }
  return (0); 
} 

Program w języku Java z najdłuższym wspólnym prefiksem przy użyciu funkcji Divide and Conquer

import java.util.Scanner;

class sum { 
    
  static String commonPrefixUtil(String str1, String str2) { 
    String result = ""; 
    int n1 = str1.length(), n2 = str2.length(); 
    for (int i = 0, j = 0; i <= n1 - 1 && j <= n2 - 1; i++, j++) 
                { 
      if(str1.charAt(i)!=str2.charAt(j)) 
                        { 
        break; 
      } 
      result += str1.charAt(i); 
    } 
    return result; 
  } 
  static String commonPrefix(String s[], int x, int y) { 
    if(x==y) 
                { 
                    return s[x]; 
    } 
    if(y>x) 
                { 
      int mid = x + (y-x)/2; 
      String s1 = commonPrefix(s, x, mid); 
      String s2 = commonPrefix(s, mid + 1, y); 
      return commonPrefixUtil(s1,s2); 
    } 
    return null; 
  } 
  public static void main(String[] args) 
        {
            Scanner sr = new Scanner(System.in);
            int n = sr.nextInt();
            String s[] = new String[n];
            for(int i=0;i<n;i++)
            {
                s[i]= sr.next();
            }
      String ans = commonPrefix(s,0,n-1); 
      if(ans.length()!=0) 
            { 
                System.out.println(ans); 
            } 
            else 
            { 
                System.out.println("-1"); 
            } 
  } 
} 
3
car 
carrace 
caramazing
car

Analiza złożoności dla najdłuższego wspólnego prefiksu przy użyciu funkcji Podziel i zwyciężaj

Złożoność czasowa

O (n * m) gdzie n to liczba ciągów i m jest długością maksymalnego ciągu. Tutaj odwiedzamy każdą postać, dlatego złożoność czasowa wynosi O (n * m).

Złożoność przestrzeni

O (m * logn) ponieważ przechowujemy wynikowy ciąg lub najdłuższy prefiks, przydzielamy miejsce, które wynosi O (m * logn).

Wywiady dotyczące projektowania systemu pękania
Translate »