[Leetcode / Javascript] 14. Longest Common Prefix

문제는 다음과 같습니다.

문자열의 배열이 주어지고 그 원소들의 가장 긴 공통 prefix(Longest Common Prefix, LCP)를 찾는 문제입니다.

여러 문자열의 LCP를 찾으려면 두 문자열 씩 비교하며 LCP를 찾아나가면 됩니다.

Example 1을 예로 들면 "flower"와 "flow"의 LCP인 "flo"를 찾고 다시 "flo"와 "flight"의 LCP인 "fl"을 찾는 방식입니다. 이렇게 찾아진 "fl"인 ["flower", "flow", "flight"]의 LCP가 됩니다.

위 예시를 식으로 나타내면 LCP(S1, S2, ... , Sn) =  LCP(LCP(S1, S2),... Sn) 이렇게 됩니다.

이 식을 코드로 나타내보겠습니다.

function LCP(left, right) {
  let prefix = left;

  while (right.indexOf(prefix) !== 0) {
    prefix = prefix.slice(0, prefix.length - 1);
    if (prefix === "") break;
  }

  return prefix;
}

function longestCommonPrefix(strs) {
  let answer = strs[0];

  for (const str of strs) {
    answer = LCP(answer, str);
    if (answer === "") break;
  }

  return answer;
}

console.log(longestCommonPrefix(["flower", "flow", "flight"]));
// fl

longestCommonPrefix() 함수에서는 strs 배열의 원소들을 순회하면서 앞에서부터 LCP를 찾아나가는 역할을 합니다.

answer 변수에 strs 배열의 첫 번째 원소를 할당하고 원소들을 하나씩 순회하면서 answer와 원소의 LCP를 찾아 다시 answer에 할당합니다. 

LCP() 함수는 두 문자열을 받아 두 문자열의 LCP를 찾는 역할을 합니다.

두 문자열 중 하나를 prefix 변수에 할당하고 다른 문자열이 그 prefix로 시작하는지 확인합니다. 만약 그 prefix로 시작하지 않는다면 prefix에서 뒤에서 한 글자씩 제거하면서 계속 확인합니다.