[LeetCode] Longest Common Prefix

이번에도 문자열 관련 문제를 풀어봤다.

문제는 간단하지만 답은 조금 생각이 필요했던 문제여서 기록해본다.

 

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

 

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.

 

Constraints:

• 1 <= strs.length <= 200
• 0 <= strs[i].length <= 200
• strs[i] consists of only lowercase English letters.

문제는 단순하다.

문자열 배열에서 가장 긴 공통 접두사를 찾는 것이다.

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

 

 

나의 풀이..

var longestCommonPrefix = function(strs) {
    let result = "";
    
    for(let i=0; i<strs[0].length; i++) {
        let prefix = strs[0].charAt(i);
        
        for(let j=1; j<strs.length; j++) {
            if(prefix != strs[j].charAt(i)) {
                return result;
            }
        }
        
        result += prefix;
    }
    
    return result;
};

 

이중 for문을 쓰고 싶지 않았지만 써야 하는 문제로 판단됐다.

그 부분을 확인하는데 시간이 조금 걸렸던 게 아쉽다.

 

첫 번째 for문은 처음 문자열 기준으로 접두사를 0부터 하나씩 대입하면서 반복을 한다.

두 번째 for문은 접두사를 가지고 두번째 문자열부터 하나씩 반복하면서 접두사를 비교한다.

접두사가 다른 문자열이 있다면 바로 result를 반환하고 종료한다.

모든 문자열의 접두사가 같으면 result에 접두사를 하나씩 더해준다.

 

조금 더 개선방법을 생각해보면..

제일 작은 길이의 문자열을 찾아서 그 기준으로 비교하는 방법도 있을 것이고

빈 문자열이나 예외 문자열이 있을 때 바로 종료하는 방법도 있을 것 같다.

 

let minLength = strs[0].length;

for(let i=1; i<strs.length; i++) {
    if(strs[i].length < minLength) {
    	minLength = strs[i].length;
    }
}

 

if(strs.length == 1) return strs[0];

 

그 외 다른 사람들 풀이를 확인해보면

postion 값을 저장해서 나중에 substring으로 접두사만 가져오는 식으로 하기도 했고 풀이 형태는 비슷했다.