[리트코드] 14. Longest Common Prefix

안녕하세요. 개발조각입니다.😊

이번에는 문제가 easy인데 제가 꼬아서 생각해서 돌고 돌다가 푼 문제입니다.ㅠ

(내가 많이 꼬인성격이라 그런가...ㅎㅎ)

---

https://leetcode.com/problems/longest-common-prefix/

Longest Common Prefix - LeetCode

 

해결방안

var longestCommonPrefix = function(strs) {
    let sortStrs = strs.sort((a,b)=> a.length - b.length);
    let short = sortStrs.shift();
    
    let answer = ''; 
    for(let i=0; i<short.length; i++){
        let str = short.slice(0, i+1);        
        let includesStr = sortStrs.filter(x => x.slice(0, i+1) === str);
        
        if(includesStr.length === sortStrs.length){
            if(answer.length < str.length) answer = str;
        }
    }
    return answer;
};

이 문제는 단순히 첫문자부터 일치하는 문자가 어디인지 찾는 문제입니다.

 

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

Input: ["reflower","flow","flight"]
Output: ""

이런 식으로 앞 문자부터 일치하는 부분을 찾으면 됩니다.

저는 이 문제가 같은부분 중에 가장 긴 문자열을 찾으라는 문제인 줄 알았습니다;;;

 

아래 예시를 토대로 설명하겠습니다.

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

 

let sortStrs = strs.sort((a,b)=> a.length - b.length);
let short = sortStrs.shift();

먼저 sort를 사용해서 strs배열의 문자열길이가 짧은 순으로 정렬했습니다.

→ sortStrs = ['flow', 'flight', 'flower']이 됩니다.

 

맨 앞자리가 가장 문자열 길이가 짧은 문자열이니 그값을 따로 빼왔습니다.

short변수 기준으로 만들생각이니 해당 short에 해당하는 문자열은 필요가 없을 것 같아 shift()로 빼주었습니다.

→ short = 'flow'

→ sortStrs = ['flight', 'flower']이 됩니다.

let answer = ''; 
for(let i=0; i<short.length; i++){
    let str = short.slice(0, i+1);        
    let includesStr = sortStrs.filter(x => x.slice(0, i+1) === str);

    if(includesStr.length === sortStrs.length){
        if(answer.length < str.length) answer = str;
    }
}
return answer;

먼저 short의 길이만큼 반복문으로 돌려주었고

short가 flow라면 str은 f → fl → flo → flow 이런 식으로 반복이 될 겁니다.

 

여기서 sortStrs에 filter을 해주어 str과 같은지 비교를 해줍니다.

sortStrs의 원소가 f → fl → flo → flow이 있는지 확인하고

다 있을 경우 answer에 넣어주는 방식으로 풀었습니다.