[leetCode] 14. Longest Common Prefix (Easy) 풀이

❓ 문제

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 "".

 

문자열 배열 중에서 가장 긴 공통 접두어를 찾는 함수를 작성하세요

만약 공통 접두어가 없다면, 빈 문자열 ""을 반환시키세요.

Example1

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

Example2

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

Constraints:

1 <= strs.length <= 200
0 <= strs[i].length <= 200
strs[i] consists of only lower-case English letters.

❗ 내 답변

/**
 * @param {string[]} strs
 * @return {string}
 */
var longestCommonPrefix = function(strs) {
    let resultStr = '';
    for (let i = 0; i < strs[0].length; i++) {
        let isAllSame = false;
        for (let j = 0; j < strs.length; j++) {
            isAllSame = strs[j][i] === strs[0][i]
            if (! isAllSame)
                return resultStr;
        }
        if (isAllSame)
            resultStr += strs[0][i];
    }
    return resultStr;
};

Runtime: 72 ms
Memory Usage: 42.3 MB

 

크게 어렵진 않았는데, 테스트 케이스를 일일이 전부 시도해보고 돌려서 성공할 수 있었다.
나만 이렇게 한번에 성공하지 못하는건가... 다들 이렇게 하는건가..? ㅜ,ㅜ

 

주어진 배열의 첫번째 문자열을 기준으로 문자열을 비교하고,
같으면 resultStr에 담고 그렇지 않으면 반환하도록 했다.

❗ Runtime이 가장 빨랐던 답변과 비교

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

    for (let word of strs) {
        while (word.indexOf(prefix) != 0) {
            prefix = prefix.substring(0, prefix.length - 1);
        }
    }

    return prefix;
};

Runtime: 73 ms
Memory Usage: 42.5 MB

 

진심 천재가 아닐까?ㅋㅋㅋㅋ
이 답변 역시 주어진 배열의 첫번째 문자열을 기준(prefix) 로 정하고 비교했다.
주어진 strs 를 반복 돌면서 각 문자들을 indexOf로 prefix 와 비교한다.
prefix는 처음엔 strs[0]의 전체 문자열이었다가 while 문을 통과하며 substring으로 뒤에서부터 하나씩 줄어들게 된다.

 

문자열 indexOf

문자열을 상대로 indexOf 를 사용했을 때 해당 비교 문자가 접두어 일 때 0을 반환하게 된다.
때문에 while 문은 하나씩 줄어든 이 prefix가 접두어인지를 확인하는 조건인 것이다.

substring

str.substring(indexStart[, indexEnd])

string 객체의 시작 인덱스로 부터 종료 인덱스 전 까지 문자열의 부분 문자열을 반환

const str = 'Mozilla';

console.log(str.substring(1, 3));
// expected output: "oz"

console.log(str.substring(2));
// expected output: "zilla"

❗ Memory 사용이 가장 적었던 답변과 비교

/**
 * @param {string[]} strs
 * @return {string}
 */
var longestCommonPrefix = function(strs) {
    if (strs.length == 0){
        return "";
    }

    let prefix = strs[0];

    for(i = 0; i < strs.length; i++){
        while(strs[i].indexOf(prefix) != 0){
            prefix = prefix.substring(0, prefix.length - 1)
        }
    }
    return prefix
};

Runtime: 78 ms
Memory Usage: 42.2 MB

 

이 답변도 마찬가지로 indexOf 를 활용했다.
Runtime이 가장 빨랐던 답변과 완전 똑같다.
다른 점은 빈 배열에 관련한 로직을 따로 정해줬다는 점이다.

💡 개선 방안

indexOf 와 substring을 적극 활용하자!