이진 검색 II를 사용한 가장 긴 공통 접두사

난이도 하드
자주 묻는 질문 어도비 벽돌 아마존 Apple 블룸버그 게시물에서 이베이 Facebook 구글 Microsoft VM웨어 Yahoo
조회수 309

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

문제 정책

“이진 검색 II를 사용하는 가장 긴 공통 접두사”문제에서 정수 값 N과 N을 지정했습니다. 문자열. 주어진 문자열의 가장 긴 공통 접두사를 인쇄하는 프로그램을 작성하십시오. 공통 접두사가 없으면 인쇄 "-1".

입력 형식

문자열 수를 나타내는 정수 값 N을 포함하는 첫 번째 줄입니다.

문자열을 포함하는 다음 N 행.

출력 형식

주어진 N 문자열의 가장 긴 공통 접두사 인 "ans"문자열을 포함하는 첫 번째 유일한 줄입니다. 그러한 접두사가 없으면 -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] |까지입니다.

5
abcde 
abba 
abaa 
abbbbb 
ababab
ab

설명 : 여기서 우리는 첫 번째와 두 번째 문자열의 공통 접두사가 "ab"임을 알 수 있습니다. 이제 이진 검색을 사용하여 다른 문자열로이 접두사를 확인하십시오. 최종 접두사 "ab"를 얻습니다.

이진 검색 II를 사용한 가장 긴 공통 접두사 알고리즘

1. 최소 길이 (L로하자)를 가진 문자열을 찾아서 입력 배열에서 Low = 0, High = L-1 인 문자열 중 하나에 대해 이진 검색을 수행합니다.

2. 왼쪽 절반의 모든 문자가 해당 색인에있는 경우 출력 교반에 문자를 추가하고 오른쪽 절반에서 검색하여 더 긴 접두사를 찾습니다.

3. 그렇지 않으면 왼쪽 절반의 문자가 해당 인덱스에 없으면 오른쪽 절반에서 검색 할 필요가 없습니다. 하지만 왼쪽 절반에서 계속 검색 (즉, 시작 인덱스에서 중간 인덱스까지)

실시

이진 검색 II를 사용하는 가장 긴 공통 접두사를위한 C ++ 프로그램

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

int min_length(vector<string> v) 
{ 
    int n=v.size();
  int mval = INT_MAX; 

  for (int i=0; i<=n-1; i++) 
    if (v[i].length() < mval) 
      mval = v[i].length(); 
  return mval; 
} 

bool allContainsPrefix(vector<string> v, int n, string str, 
          int start, int end) 
{ 
  for (int i=0; i<=n-1; i++) 
    for (int j=start; j<=end; j++) 
      if (v[i][j] != str[j]) 
        return (false); 
  return (true); 
} 

string common_prefix(vector<string> v) 
{ 
    int n=v.size();
  int index = min_length(v); 
  string prefix; 
  int low = 0, high = index; 

  while (low <= high) 
  { 
    int mid = low + (high - low) / 2; 
    if(allContainsPrefix (v, n, v[0], low, mid)) 
    { 
      prefix = prefix + v[0].substr(low, mid-low+1); 
      low = mid + 1; 
    } 
    else 
    {
        high = mid - 1;
    }
  } 
  return prefix; 
} 

int main() 
{ 
    int n;
    cin>>n;
    vector<string> v;
    for(int i=0;i<n;i++)
    {
        string x;
        cin>>x;
        v.push_back(x);
    }
    string ans = common_prefix(v);
  if(ans.length()) 
  {
      cout<<ans<<endl;
  }
  else
  {
      cout<<-1<<endl; 
  }
  return (0); 
} 

이진 검색 II를 사용하는 가장 긴 공통 접두사를위한 Java 프로그램

import java.util.Scanner;
import java.util.Vector;
class sum
{
    public static int findMinLength(Vector<String> v) 
    { 
        int n=v.size();
  int min = Integer.MAX_VALUE; 
  for (int i = 0; i <= (n - 1); i++) 
  { 
    if (v.get(i).length() < min) { 
      min = v.get(i).length(); 
    } 
  } 
  return min; 
    }
    public static boolean allContainsPrefix(Vector<String> v, int n, String str, int start, int end) 
  { 
    for (int i = 0; i <= (n - 1); i++) 
    { 
      String arr_i = v.get(i); 
      
      for (int j = start; j <= end; j++) 
        if (arr_i.charAt(j) != str.charAt(j)) 
          return false; 
    } 
    return true; 
  }
    public static String common_prefix(Vector<String> v)
    {
                int n=v.size();
                int index = findMinLength(v); 
    String prefix = "";
    int low = 0, high = index-1; 
    while(low <= high){ 
      int mid = low + (high - low)/2; 
      if(allContainsPrefix(v, n, v.get(0), low, mid)==true) 
      { 
        prefix = prefix + v.get(0).substring(low, mid + 1); 
        low = mid + 1; 
      } 
      else 
      { 
        high = mid - 1; 
      } 
    } 
    return prefix; 
    }
    public static void main(String[] args)
    {
        Scanner sr = new Scanner(System.in);
        int n=sr.nextInt();
        Vector<String> v = new Vector<String>(n+1);
        for(int i=0;i<n;i++)
        {
            String x = sr.next();
            v.add(x);
        }
        String ans = common_prefix(v);
        if(ans.length()!=0)
        {
            System.out.println(ans);
        }
        else
        {
            System.out.println("-1");
        }
    }
}
5
abcde 
abcd 
abcdefgh 
abcqwer 
abcdhfdiefi
abc

이진 검색 II를 사용한 가장 긴 공통 접두사에 대한 복잡성 분석

시간 복잡성

O (n * m * logm) 어디에 n 총 문자열 수이며 m 최대 문자열의 길이입니다. 논리의 반복 관계는 T (m) = T (m / 2) + O (m * n)입니다.

공간 복잡성

O (m) 어디에 m 최대 문자열의 길이입니다. 이 공간을 사용하여 문자열 간의 작업을 수행 한 후 공통 접두사를 저장합니다.

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