Longest Common Prefix

이 문제는 여러 문자열이 공통으로 가지는 가장 긴 접두사(prefix)를 찾는 문제다.

접두사는 문자열의 중간이 아니라 항상 첫 문자부터 시작하는 연속된 부분 문자열이다. 예를 들어 flower의 접두사는 f, fl, flo, …, flower가 될 수 있지만 low는 접두사가 아니다.

이 정의 덕분에 가능한 답을 모든 부분 문자열에서 찾을 필요가 없다. 공통 접두사는 반드시 첫 번째 문자열의 접두사이므로, 첫 번째 문자열을 기준으로 각 위치의 문자가 모든 문자열에서 같은지만 확인하면 된다.

세로로 문자 비교하기

다음 입력을 생각해보자.

flower
flow
flight

문자열을 세로로 놓고 같은 인덱스의 문자를 비교한다.

index    0  1  2  3  4  5
         -----------------
flower   f  l  o  w  e  r
flow     f  l  o  w
flight   f  l  i  g  h  t
         ✓  ✓  ✗

인덱스 0의 문자는 모두 f다.
인덱스 1의 문자는 모두 l이다.
인덱스 2에서는 o와 i가 다르다.

따라서 인덱스 2부터는 공통 접두사가 될 수 없고, 그 직전까지인 fl이 답이다.

여기서 중요한 점은 한 위치에서 불일치를 발견하면 즉시 탐색을 끝낼 수 있다는 것이다. 접두사는 첫 문자부터 끊김 없이 이어져야 하므로, 뒤쪽 문자가 다시 같아지는지는 답에 영향을 주지 않는다.

탐색 기준 세우기

첫 번째 문자열 strs[0]을 기준 문자열로 사용한다. 기준 문자열의 각 문자에 대해 나머지 모든 문자열을 순회하며 다음 두 조건을 확인한다.

현재 문자열이 해당 인덱스까지 도달하지 못했다.
같은 인덱스의 문자가 기준 문자열의 문자와 다르다.

둘 중 하나라도 만족하면 현재 위치에서 공통 접두사가 끝난다.

기준 문자열의 각 인덱스 index에 대해:
    모든 문자열을 확인한다.

    문자열의 길이가 index와 같거나
    index 위치의 문자가 기준 문자와 다르면:
        기준 문자열의 0부터 index 직전까지 반환한다.

기준 문자열을 끝까지 확인했다면:
    기준 문자열 전체를 반환한다.

길이 검사도 문자 비교만큼 중요하다. 예를 들어 dog와 do를 비교할 때 두 번째 문자열에는 인덱스 2의 문자가 없다. 이 경우 문자 불일치와 마찬가지로 공통 접두사는 do에서 끝난다.

풀이

function longestCommonPrefix(strs: string[]): string {
  const first = strs[0];

  for (let index = 0; index < first.length; index++) {
    const char = first[index];

    for (let wordIndex = 1; wordIndex < strs.length; wordIndex++) {
      const word = strs[wordIndex];

      if (index === word.length || word[index] !== char) {
        return first.slice(0, index);
      }
    }
  }

  return first;
}

왜 가장 긴 접두사가 되는가?

루프가 인덱스 index에 도달했다는 것은 0부터 index - 1까지의 문자가 모든 문자열에서 같다는 뜻이다. 따라서 first.slice(0, index)는 공통 접두사다.

현재 위치에서 길이가 부족하거나 다른 문자를 발견했다면, 이 위치를 포함하는 문자열은 공통 접두사가 될 수 없다. 그보다 긴 접두사 역시 현재 위치를 반드시 포함하므로 답이 될 수 없다. 따라서 바로 직전까지 확인한 접두사가 가장 길다.

불일치 없이 기준 문자열의 끝까지 도달한 경우에는 첫 번째 문자열 전체가 공통 접두사다. 공통 접두사는 첫 번째 문자열보다 길 수 없으므로 이때도 가장 긴 답이 된다.

복잡도

첫 번째 문자열의 길이를 m, 문자열의 개수를 n이라고 하면 최악의 경우 모든 위치에서 모든 문자열을 비교한다.

시간 복잡도: O(n × m)
공간 복잡도: O(1)

조금 더 정확히 말하면 시간은 불일치가 발견될 때까지 실제로 비교한 문자 수에 비례한다. 앞부분에서 문자가 달라지면 즉시 반환하므로 불필요한 비교를 하지 않는다.

핵심 인사이트

이 문제에서 공통 접두사를 별도로 만들어가며 관리할 필요는 없다. 이미 첫 번째 문자열 안에 모든 정답 후보가 들어 있기 때문이다.

공통 접두사는 반드시 임의의 한 문자열의 접두사다. 하나의 문자열을 기준으로 삼고, 앞에서부터 후보가 유효한 범위만 확인한다.

이처럼 답의 후보가 입력 하나의 일부로 제한되는 문제에서는 새 후보를 생성하기보다, 기준을 하나 정한 뒤 후보 범위를 줄여가는 방식으로 풀이를 단순화할 수 있다.