단어 별 일치를 사용하는 가장 긴 공통 접두사


난이도 중급
자주 묻는 질문 VM웨어
배열

단어 목록이 주어지면 모든 단어의 가장 긴 공통 접두사를 단어 단위로 찾습니다.

입력:
list [] = {“apple”,“ape”,“april”}
출력:
ap
입력:
list [] = {“star”,“stole”,“steam”,“start”}
출력:
st

가장 긴 공통 접두사 알고리즘

두 단어의 가장 긴 공통 접두사는 다음과 같습니다.
W1을 첫 번째 단어로 W2를 두 번째 단어로,

  1. 초기화 변수 commonPrefix는“”(빈 문자열)입니다.
  2. 단어 중 하나의 끝에 도달 할 때까지 W1과 W2에서 동시에 횡단을 시작합니다.
  3. W1 및 W2의 문자를 일치 시키십시오 (동일한 경우 commonPrefix에 추가하고 두 단어 모두 앞으로).
  4. 그렇지 않으면 commonPrefix를 반환합니다.

위의 알고리즘을 확장하여 N 단어 목록의 가장 긴 공통 접두사를 찾을 수 있습니다.

  1. 문자열 변수 commonPrefix를 목록의 첫 번째 단어로 초기화합니다.
  2. 인덱스 1 (o 기반 인덱싱)부터 목록을 순회합니다.
  3. commonPrefix를 commonPrefix의 공통 접두사 및 목록의 현재 단어로 업데이트합니다.
  4. 순회가 끝나면 commonPrefix를 반환합니다.

가장 긴 공통 접두사에 대한 설명

예를 들어,
list [] = {“star”,“stole”,“steam”,“start”}

단계 1
commonPrefix =“별표”

단계 2
인덱스 3에서 목록 끝까지 목록을 탐색하는 동안 4 단계와 1 단계를 반복합니다.

3 단계와 4 단계
반복 1
commonPrefix = (commonPrefix, "stole")의 공통 접두사
commonPrefix = "st"
반복 2
commonPrefix = (commonPrefix,“steam”)의 공통 접두사
commonPrefix = "st"
반복 3
commonPrefix = (commonPrefix, "start")의 공통 접두사
commonPrefix = "st"

우리는 목록을 순회했고 목록에있는 모든 단어의 공통 접두사는 "st"입니다. 자세한 내용은 아래 이미지를 참조하십시오.

단어 별 일치를 사용하는 가장 긴 공통 접두사

JAVA 코드

public class LongestCommonPrefixUsingWordByWordMatching {
    // Function to find common prefix of two words
    private static String prefix(String W1, String W2) {
        // Initialize prefix as empty string
        String prefix = "";

        int n1 = W1.length();
        int n2 = W2.length();
        int i = 0, j = 0;

        // Traverse in W1 and W2 simultaneously
        while (i < n1 && j < n2) {
            // If characters of W1 and W2 are equal, append it to answer else return prefix
            if (W1.charAt(i) == W2.charAt(j)) {
                prefix += W1.charAt(i);
                i++;
                j++;
            } else {
                return prefix;
            }
        }

        // All words matched, return prefix
        return prefix;
    }

    private static String longestCommonPrefix(String[] list) {
        // Initialize longest common prefix as first word of list
        String lcp = list[0];
        
        // Traverse the list from index 1 (0 based indexing)
        for (int i = 1; i < list.length; i++) {
            // Update lcp as prefix of lcp and current word
            lcp = prefix(list[i], lcp);
        }
        
        // return lcp
        return lcp;
    }

    public static void main(String[] args) {
        // Example 1
        String list1[] = new String[] {"apple", "ape", "april"};
        System.out.println(longestCommonPrefix(list1));

        // Example 2
        String list2[] = new String[] {"star", "stole", "steam", "start"};
        System.out.println(longestCommonPrefix(list2));
    }
}

가장 긴 공통 접두사에 대한 C ++ 코드

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

// Function to find common prefix of two words
string prefix(string W1, string W2) {
    // Initialize prefix as empty string
    string prefix = "";
    
    int n1 = W1.size();
    int n2 = W2.size();
    int i = 0, j = 0;
    
    // Traverse in W1 and W2 simultaneously
    while (i < n1 && j < n2) {
        // If characters of W1 and W2 are equal, append it to answer else return prefix
        if (W1[i] == W2[j]) {
            prefix += W1[i];
            i++;
            j++;
        } else {
            return prefix;
        }
    }

    // All words matched, return prefix
    return prefix;
}

string commonPrefix(vector<std::string> &list) {
    // Initialize longest common prefix as first word of list
    string lps = list.front();
    
    // Traverse the list from index 1 (0 based indexing)
    for (auto itr = list.begin() + 1; itr != list.end(); itr++) {
        // Update lcp as prefix of lcp and current word
        lps = prefix(lps, *itr);
    }
    
    // return lcp
    return lps;
}

int main() {
    // Example 1
    vector<std::string> list1;
    list1.push_back("apple");
    list1.push_back("ape");
    list1.push_back("april");
    cout<<commonPrefix(list1)<<endl;
    
    // Example 2
    vector<std::string> list2;
    list2.push_back("star");
    list2.push_back("stole");
    list2.push_back("steam");
    list2.push_back("start");
    cout<<commonPrefix(list2)<<endl;
    
    return 0;
}
ap
st

가장 긴 공통 접두사에 대한 복잡성 분석

시간 복잡성 = O (N * 목록에서 단어의 최대 길이) 
공간 복잡성 = O (1)
여기서 N은 목록의 총 단어 수입니다.

참조