Divide and Conquer를 사용하는 가장 긴 공통 접두사

난이도 하드
자주 묻는 질문 Accenture 수행자 아마존 광신자 구글
분열과 정복 조회수 402

시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.

문제 정책

“나누기 및 정복을 사용하는 가장 긴 공통 접두사”문제에서 정수 n과 n을 지정했습니다. 문자열. 가장 긴 공통 접두사를 인쇄하는 프로그램을 작성하십시오. 공통점이 없다면 접두사 그런 다음“-1”을 인쇄하십시오.

입력 형식

첫 번째 줄에는 정수 n이 포함됩니다.

각각 하나의 문자열을 포함하는 다음 n 줄.

출력 형식

주어진 문자열의 가장 긴 공통 접두사를 나타내는 문자열을 인쇄합니다. 그러한 접두사 문자열이 없으면“-1”을 인쇄하십시오.

제약

  • 1 <= n <= 10 ^ 3
  • 1 <= | s [i] | <= 10 ^ 3 여기서 i는 0에서 n-1까지입니다.
  • s [i] [j]는 소문자 영어 알파벳이어야합니다. 여기서 i는 0에서 n-1까지, j는 0에서 | s [i] |까지입니다.

3
tutorial 
tutcup 
turnin
tu

설명 : 여기서 우리는 "tu"가 모든 문자열에 나타나는 접두사임을 볼 수 있습니다.

Divide and Conquer를 사용한 가장 긴 공통 접두사 알고리즘

이 알고리즘에서는 분할 및 정복 접근 방식에 대해 설명합니다. 먼저 문자열 배열을 두 부분으로 나눕니다. 그런 다음 왼쪽 부분과 오른쪽 부분에 대해 동일한 작업을 수행합니다. 모든 문자열의 길이가 1이되지 않을 때까지이를 수행 할 것입니다. 이제 그 후에 왼쪽 및 오른쪽 문자열의 공통 접두사를 반환하여 정복을 시작합니다.

1. 길이가 1이 될 때까지 문자열 배열을 두 부분으로 재귀 적으로 나눕니다.

2. 이제 왼쪽과 오른쪽 문자열의 공통 접두사를 반환하여 정복을 시작하십시오.

실시

Divide and Conquer를 사용하는 가장 긴 공통 접두사를위한 C ++ 프로그램

#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); 
} 

Divide and Conquer를 사용하는 가장 긴 공통 접두사를위한 Java 프로그램

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

Divide and Conquer를 사용한 가장 긴 공통 접두사에 대한 복잡성 분석

시간 복잡성

O (n * m) 어디에 n 문자열의 수이며 m 최대 문자열의 길이입니다. 여기서 우리는 시간 복잡도가 O (n * m) 인 모든 캐릭터를 방문합니다.

공간 복잡성

O (m * logn) 결과 문자열 또는 가장 긴 접두사 문자열을 저장하기 때문에 O (m * logn) 인 공간을 할당합니다.

균열 시스템 설계 인터뷰
Translate »