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

 

문자열 배열 중에서 가장 긴 공통 접두사 문자열을 찾는 함수를 작성하자.

공통된 접두사가 없으면 빈 문자열 ""을 반환한다.

Example 1:

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

Example 2:

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

 

❗ 내 풀이

처음에는 어떻게 비교해서 공통 문자를 넣어야 할지 고려할 부분이 많아 막막했는데,

생각의 전환으로 문자를 제외하는 방식으로 개발하면 더 쉬울 것 같아

배열의 첫 문자열을 넣고 그다음 인덱스의 문자열과 비교하여 다르면 문자를 자르는 방식으로 개발하였다.

/**
 * @param {string[]} strs
 * @return {string}
 */
var longestCommonPrefix = function(strs) {
    let comPrefix = strs[0];
    
    for(let i = 1 ; i < strs.length ; i++) {
        for(let j = 0 ; j < comPrefix.length ; j++) {
            if(comPrefix[j] !== strs[i][j]) {
                comPrefix = comPrefix.substring(0, j);
            }
        }
    }
    return comPrefix;
};

Runtime: 106ms
Memory Usage: 42.3 MB

 

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

/**
 * @param {string[]} strs
 * @return {string}
 */
var longestCommonPrefix = function(strs) {
    if (strs.length === 0) return "";
    let prefix = strs[0];
    
    for (let i = 1; i < strs.length; i++) {
        while (strs[i].indexOf(prefix) != 0) {
            prefix = prefix.substr(0, prefix.length - 1);
        }    
    }   
    
    return prefix;
};

 

길이가 0이면 ""값을 리턴해주었는데 문제 조건이 아래와 같아서 해당 코드는 필요 없을 것 같다. 그러나 실제 코드에서는 있으면 런타임 속도를 높여줄 수 있으니 길이가 0일 경우도 반드시 생각해두자.

문제 조건 : 

• 1 <= strs.length <= 200
• 0 <= strs[i].length <= 200

또한, 나는 for문을 주구장창 쓰는 것 같다. 다른 예제를 보면 while을 사용하여 돌린 부분도 있으니 for문 외 반복문을 생각해보자.

 

알게 된 점

1. indexOf()함수에 문자열이 들어갈 수 있다.

문자로만 테스트하고 문자만 들어갈 수 있다고 생각했는데 문자열도 들어갈 수 있었다. 비교 문자열을 포함하고 있으면 시작하는 부분의 index를 리턴하고, 해당 문자열을 포함하지 않으면 -1을 리턴한다.

예제 결과값을 한번 살펴보자.

let str1 = "flower";
let str2 = "abflower";
let str3 = "abcd"
let dif = "flow";

// str1.indexOf(dif)
console.log(str1.indexOf(dif)); // output : 0

// str2.indexOf(dif)
console.log(str2.indexOf(dif)); // output : 2

// str3.indexOf(dif)
console.log(str3.indexOf(dif)); // output : -1

 

 

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

/**
 * @param {string[]} strs
 * @return {string}
 */
var longestCommonPrefix = function(strs) {
    
    if (!strs.length)        return "";
    
    let prefix = strs[0];
    
    for (let i = 1; i < strs.length; i++) {
        
        while (strs[i].indexOf(prefix) != 0) {
               
            prefix = prefix.slice(0, prefix.length - 1);
            
            if (prefix.length == 0)     return "";
        }
    }
    
    return prefix;
};

Runtime이 가장 빨랐던 답변과 비교하였을 때,

• strs.length를 비교하는 방식
• substr을 slice를 사용한 것
• while문 사이에 if(prefix.length == 0) 이면 ""을 리턴하는 것

외에는 거의 동일하였다.

 

🚩 Detail

• 날짜 : 2022.03.15
• 난이도 : Easy
• 제목 : Longest Common Prefix
• URL : https://leetcode.com/problems/longest-common-prefix/