[알고리즘 - LeetCode] 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 "".
Note: All given inputs are in lowercase letters a-z.

a-z의 소문자 알파벳으로 단어들로 구성된 배열이 주어졌을 때, 모든 문자열에 공통되는 가장 긴 접미사를 리턴하라. 접미사가 없는 경우에는 빈 문자열을 리턴하라

Example 1:

Input: ["flower","flow","flight"]
Output: "fl"

Example 2:

Input: ["dog","racecar","car"]
Output: ""
Explanation: There is no common prefix among the input strings.

풀이

제출 코드

const longestCommonPrefix = function(strs) {
    if (!strs.length) return "";
    
    const standard = strs[0];
    
    for (let i = 0; i < standard.length; i++) {
        const prefix = standard.slice(0, standard.length - i);
        
        for (let j = 0; j < strs.length; j++) {
            if (!strs[j].startsWith(prefix)) {
                break;
            }
            if (j === strs.length - 1) {
                return prefix;
            }
        }
    }
    return "";
};

1. 첫번째 for 문에서는 배열의 0번째 인덱스를 기준으로 설정하여 문자열의 길이를 줄여간다.
2. 두번째 for 문에서는 전체 배열을 순회하며 기준으로 설정한 값이 startsWith로 true값이 나오지 않을 때
3. break;로 두번째 순회를 빠져나고 기준 값의 길이를 줄여서 재설정하고 반복한다.

기준으로 잡는 문자열의 길이를 줄여서 배열의 모든 문자열을 확인해야 하기 때문에 for문을 두 번 사용할 수 밖에 없었다.

실행 속도가 좀 더 빠른 코드들을 보아도 for/ while문 혹은 for문/ every 메소드로 두 번씩 순회 했다.

타 제출 코드와 실행 속도 비교

코드워즈와 달리 리트코드는 테스트 내용을 보면서 코드를 짤 수 없어서 제출을 했을 때 edge case들을 확인하게 되는데 배열이 주어지는 문제에서는 빈 배열 확인해서 early return하는 것이 무조건이다. (85ms에서 60ms으로... 15ms의 향상....)

개선 사항

몇몇 타 코드들를 살펴보니 내가 startsWith메소드를 사용했던 부분에 indexOf를 사용하는 게 많아서 크게 흥미가 안생기길래 mdn에서 startsWith와 endsWith를 다시 살펴봤다.

참고

startsWith와 endsWith

매개변수로 들어가는 위치의 문자열로 시작 / 끝나는지를 확인하여 Boolean값을 반환한다.
문자열을 확인하는 위치가 문자열의 시작과 끝으로 정해진 것을 제외하고는 includes메소드와 유사하다.

이전에 희한한 (정말 희한했던) 코드워즈 문제를 풀다가 다른 분의 풀이를 보고 알게 된 메소드들인데 그 이후 문자열 확인이 필요할 때에는 항상 떠올라서 종종 잘 사용하고 있다.

참고 mdn startsWith, mdn endsWith