Longest Common Prefix

Q: 최장 공통 접두사의 시간 복잡도는 얼마인가요?

두 스캔 모두 O(S) 시간에 실행되며, 여기서 S 는 전체 문자의 수입니다. 답을 제외한 추가 메모리는 O(1) 입니다. 열 스캔은 길이가 L 인 답에 대해 n × (L+1) 로도 제한되므로, 단어가 앞부분에서 서로 다르면 일찍 중단됩니다.

Q: 공통 접두사가 없을 때 Longest Common Prefix는 무엇을 반환해야 하나요?

빈 문자열 "" 입니다. 두 단어가 서로 다른 글자로 시작하면 바로 이렇게 됩니다. 예를 들어 stack , queue , heap 이 있습니다.

Q: 가로 스캔과 세로 스캔 중 어느 것이 더 나을까요?

둘 다 최악의 경우 시간 복잡도는 O(S) 로 같습니다. 수직 스캔이 더 안전한 선택입니다. 단어 하나라도 일치하지 않는 첫 번째 열에서 멈추지만, 수평 스캔은 뒤쪽의 단어 하나가 비교를 끝내기 전까지 여러 단어와 긴 접두사를 비교할 수 있습니다.

쉬움배열과 문자열

+10

단어 배열 strs가 주어집니다. 모든 단어가 시작하는 가장 긴 문자열을 반환하세요. 모든 단어가 같은 문자로 시작하지 않으면 빈 문자열 ""을 반환하세요. 단어는 자기 자신의 접두사로 간주되므로, 단어가 하나뿐이면 그 단어가 정답입니다.

함수

longestCommonPrefix(strs: string-array) → string

strsstring-array: 비교할 단어
반환값string: 모든 단어가 공유하는 가장 긴 접두사 또는 빈 문자열

제약 조건

1 ≤ strs.length ≤ 200
1 ≤ strs[i].length ≤ 200
모든 단어에는 소문자 영어 알파벳만 포함됩니다.

예제

입력: strs = ["interview", "internet", "interval", "internal"]
출력: "inter"
설명: 네 단어 모두 inter로 시작합니다. 다음 위치에서 interview와 interval에는 v가 있고, internet과 internal에는 n이 있으므로 접두사는 그 지점에서 끝납니다.

입력: strs = ["stack", "queue", "heap"]
출력: ""
설명: 단어는 s, q, h로 시작합니다. 첫 글자부터 일치하지 않으므로 답은 비어 있습니다.

입력: strs = ["prefix", "pre", "prepare"]
출력: "pre"
설명: pre가 가장 짧은 단어이고 나머지 두 단어가 이 단어로 시작하므로, 이것이 답의 전부입니다. 공통 접두사는 가장 짧은 단어보다 길 수 없습니다.

후속 질문

목록이 고정된 상태에서 많은 검색어가 들어온다고 가정해 보세요. 목록을 다시 훑지 않고 각 검색어와 목록의 어떤 단어가 공유하는 가장 긴 접두사를 어떻게 찾을 수 있을까요?

힌트

하나씩 열어 보세요. 열 때마다 조금 더 알려 줍니다.

3개 중 0개 열림

풀이

모든 단어에서 같은 위치에 해당 글자가 있을 때만 그 글자를 정답에 포함하며, 단어들 사이에 글자가 다르거나 단어가 끝나는 첫 번째 위치에서 정답도 끝납니다. 두 접근 방식은 서로 다른 순서로 단어를 한 글자씩 읽습니다. 열을 기준으로 살펴보면 처음으로 글자가 다른 지점에서 멈춥니다.

접두사를 단어별로 줄이기

핵심 아이디어

첫 번째 단어 전체가 답이라고 가정하세요. 그 단어를 두 번째 단어와 공통으로 갖는 부분까지 줄이고, 그런 다음 세 번째 단어와 공통으로 갖는 부분까지 줄이는 식으로 진행하세요. 여러 단어의 공통 접두사는 처음 두 단어의 공통 접두사에서 시작해, 그 결과와 세 번째 단어의 공통 접두사를 구하는 방식으로 이어집니다. 각 단계에서는 접두사를 유지하거나 줄일 수만 있습니다. 예를 들어 1의 경우 후보는 두 번째 단어를 처리한 뒤 interview에서 inter로 줄어들고 그대로 유지됩니다.

각 문자는 최대 한 번만 비교되므로, 전체 S개 문자를 기준으로 시간 복잡도는 O(S)입니다. 약점은 순서입니다. 첫 글자만 다른 마지막 단어를 포함해 글자 수가 200인 단어 200개가 있으면, 마지막 단어가 접두사를 아무것도 남지 않게 줄이기 전까지 거의 40,000번 비교하게 됩니다.

알고리즘

prefixLen을 strs[0]의 길이로 설정합니다.
다른 각 단어에 대해 prefixLen까지 strs[0]과 공유하는 앞부분의 글자 수를 셉니다.
prefixLen을 그 수로 설정하고, 0이 되면 일찍 중단합니다.
strs[0]의 처음 prefixLen개 글자를 반환합니다.

def longestCommonPrefix(strs):
    first = strs[0]
    prefix_len = len(first)
    for word in strs[1:]:
        common = 0
        while common < prefix_len and common < len(word) and word[common] == first[common]:
            common += 1
        prefix_len = common
        if prefix_len == 0:
            break
    return first[:prefix_len]

열별로 비교하세요

핵심 아이디어

단어들을 표처럼 한 번에 한 열씩 읽습니다. 현재 열에서 strs[0]의 문자를 확인하고, 다른 모든 단어에도 그 위치에 같은 문자가 있는지 살펴봅니다. 어떤 단어의 문자가 처음으로 다르거나 해당 열까지 길이가 짧으면, 정답은 그 열까지의 strs[0]입니다.

정답은 모든 단어의 문자가 일치하는 열이 이어진 부분과 정확히 같으며, 이 루프는 그 부분을 왼쪽부터 따라가다가 일치가 깨지는 지점에서 멈춥니다. 끝까지 일치가 깨지지 않으면 strs[0]이 정답입니다.

n개의 단어가 있고 정답의 길이가 L일 때, 루프는 최대 n × (L+1)번 확인하며, 이는 O(S)이기도 합니다. 200개 단어 중 마지막 단어의 첫 글자만 다른 경우에는 199번 비교한 뒤 멈춥니다.

알고리즘

first를 strs[0]으로 둡니다.
열 col을 0부터 first의 길이에서 1을 뺀 값까지 순회하며 first[col]을 읽습니다.
다른 각 단어에 대해, col 위치에 문자가 없거나 해당 문자가 다르면 first의 처음 col개 문자를 반환합니다.
모든 열이 일치하면 first를 반환합니다.

def longestCommonPrefix(strs):
    first = strs[0]
    for col in range(len(first)):
        for word in strs[1:]:
            if col == len(word) or word[col] != first[col]:
                return first[:col]
    return first

함정과 경계 사례

더 짧은 단어의 끝을 넘어 읽는 것. prefix, pre, prepare에서 열 3은 prefix에는 있지만 pre에는 없습니다. 문자를 읽기 전에 길이를 확인하세요.
정렬하지 않고 첫 번째 단어와 마지막 단어만 비교하는 것. abc, xbd, abd에서 첫 번째 단어와 마지막 단어는 ab를 공유하지만, xbd가 열 0에서 일치하지 않으므로 답은 빈 문자열입니다.
아무것도 공유되지 않을 때 null이나 자리 표시자를 반환하는 것. 답은 빈 문자열입니다.
단어 하나는 그 자체가 접두사라는 점을 잊는 것: algorithm 하나만 있으면 algorithm을 반환합니다.
불변 문자열에 문자를 한 번에 하나씩 추가하는 것. 그러면 길이가 200인 답을 만드는 데 200번 복사해야 합니다. 길이를 기록하고 첫 번째 단어에서 한 번 잘라내세요.

자주 묻는 질문4

최장 공통 접두사의 시간 복잡도는 얼마인가요?

두 스캔 모두 O(S) 시간에 실행되며, 여기서 S는 전체 문자의 수입니다. 답을 제외한 추가 메모리는 O(1)입니다. 열 스캔은 길이가 L인 답에 대해 n × (L+1)로도 제한되므로, 단어가 앞부분에서 서로 다르면 일찍 중단됩니다.

단어를 정렬하여 가장 긴 공통 접두사를 찾을 수 있나요?

맞습니다. 알파벳순으로 정렬하면 첫 번째 단어와 마지막 단어 사이의 모든 단어는 두 단어가 공유하는 글자로 시작하므로, 이 두 단어만 비교하면 답을 얻을 수 있습니다. 정렬은 약 n log n개의 단어 쌍을 비교하므로 한 번 훑는 것보다 비용이 더 들지만, 코드는 짧습니다.

공통 접두사가 없을 때 Longest Common Prefix는 무엇을 반환해야 하나요?

빈 문자열 ""입니다. 두 단어가 서로 다른 글자로 시작하면 바로 이렇게 됩니다. 예를 들어 stack, queue, heap이 있습니다.

가로 스캔과 세로 스캔 중 어느 것이 더 나을까요?

둘 다 최악의 경우 시간 복잡도는 O(S)로 같습니다. 수직 스캔이 더 안전한 선택입니다. 단어 하나라도 일치하지 않는 첫 번째 열에서 멈추지만, 수평 스캔은 뒤쪽의 단어 하나가 비교를 끝내기 전까지 여러 단어와 긴 접두사를 비교할 수 있습니다.

def longestCommonPrefix(strs):
    # 여기에 코드를 작성하세요

테스트 #1

테스트 #2

테스트 #3

인자

strs = ["interview", "internet", "interval", "internal"]

예상 출력

"inter"