[LeetCode 14] Longest Common Prefix - 가장 긴 공통 접두사 구하기

[LeetCode 14] Longest Common Prefix - 가장 긴 공통 접두사 구하기

📌 문제 설명

주어진 문자열 배열에서 가장 긴 공통 접두사를 찾아 반환하는 문제입니다.

🔹 문제 원문

Write a function to find the longest common prefix string amongst an array of strings.
If there is no common prefix, return an empty string "".
You may assume that all strings consist of lowercase English letters only.

🔹 해석

• 문자열 배열에서 가장 긴 공통 접두사를 찾는 함수를 작성하라.
• 공통 접두사가 없다면 빈 문자열 ""을 반환한다.
• 모든 문자열은 소문자 알파벳으로만 구성된다.

🔹 단어 정리

단어 뜻

prefix	접두사
amongst	~중에서
consist of	~로 이루어져 있다
assume	가정하다
lowercase	소문자

---

✅ 내가 작성한 코드

export function longestCommonPrefix(strs: string[]): string {
  const lens = strs.map((str) => str.length);
  const len = lens.reduce((acc, cur) => Math.min(acc, cur), Infinity);

  for (let i = 0; i <= len; i++) {
    if (i === len) {
      return strs[0].slice(0, i);
    }

    const char = strs[0][i];
    for (let j = 1; j < strs.length; j++) {
      if (strs[j][i] !== char) {
        return strs[0].slice(0, i);
      }
    }
  }

  return "";
}

✅ 풀이 요약

• 모든 문자열의 길이 중 가장 짧은 값을 기준으로 반복
• 인덱스를 하나씩 증가시키며 문자열 배열의 같은 위치 문자가 모두 같은지 비교
• 다를 경우 그 이전까지가 공통 접두사 → slice(0, i) 반환

---

✅ 테스트 코드 (Jest)

describe("Easy 14: Longest Common Prefix", () => {
  it("has common prefix", () => {
    expect(longestCommonPrefix(["flower", "flow", "flight"])).toEqual("fl");
  });

  it("has no common prefix", () => {
    expect(longestCommonPrefix(["dog", "racecar", "car"])).toEqual("");
  });

  it("has one string", () => {
    expect(longestCommonPrefix(["a"])).toEqual("a");
  });

  it("shorter string first", () => {
    expect(longestCommonPrefix(["ab", "a"])).toEqual("a");
  });
});

---

📈 시간 및 공간 복잡도

항목 복잡도

시간	O(N × M) (N: 문자열 개수, M: 최소 문자열 길이)
공간	O(1) (별도 배열 저장 없이 연산만 수행)

---

✅ 마무리 정리

• 문자열 하나하나 비교하는 기본적인 접근이지만, 매우 안정적
• 사전순 정렬보다 효율적일 수 있음 (불필요한 연산 제거)
• 배열 탐색 & 문자열 비교 문제에서 기본기 다지기 좋은 문제