[Reet code] Longest Common Prefix

Details

Intuition

문자열을 두개씩 비교하면서 접두사를 찾는다. 두 문자열중에서 길이가 더 짧은 것의 인덱스까지만 탐색한다.

Approach

문자열 리스트를 순회하면서 접두사가 변하기 때문에 접두사를 저장해야한다. 처음에는 접두사 그 자체로, 즉 문자열로 저장했더니 통과는 되었지만 메모리를 많이 잡아먹었다.

이 방법은 접두사를 문자열 대신 인덱스로 저장해서 문자열이 아무리 길더라도 0~200 사이의 정수만 저장하게 되므로 메모리를 훨씬 적게 사용한다.

Complexity

• Time complexity: O(NM)
  N 은 리스트의 길이, M 은 문자열의 길이를 의미한다.

• Space complexity: O(1)
  number 인 LCPIdx 과 shortLen 를 저장해야 한다. 둘다 0~200 사이의 정수이다. 함수 호출 스택도 쌓이지 않으니 O(1) 이라 할 수 있겠다.

Code

const getPrefixIndex = (str1: string, str2: string) => {
    const shortLen = Math.min(str1.length, str2.length)
    for (let i=0; i < shortLen; i++) {
        if (str1[i] !== str2[i]) {
            return i-1
        }
    }
    return shortLen - 1
}

function longestCommonPrefix(strs: string[]): string {
    let LCPIdx = 200
    for (let i=0; i < strs.length - 1; i++) {
        LCPIdx = Math.min(LCPIdx, getPrefixIndex(strs[i], strs[i+1]))
    }
    return strs[0].slice(0, LCPIdx+1)
};