[Array] Longest Common Prefix

from leetcode

 

 

나의 답

function longestCommonPrefix(strs: string[]): string {

    let preStr: string = strs[0]

    for (const str of strs) {
        if (str.length < preStr.length) {
            preStr = str
        }
    }

    let prefix = ""
    for (let i = 0; i < preStr.length; i++) {
        let count = 0
        for (const str of strs) {
            if (str[i] == preStr[i]) count++
        }

        if(count==strs.length) prefix+=preStr[i]
        else return prefix
    }
    return prefix
};

시간복잡도 / 메모리 거의 최하위 ㅋㅋ

 

1. 문제접근

strs배열에서 가장 짧은 string을 찾는다 (prefix이므로, 가장 긴 prefix의 길이는 가장 짧은 string을 넘을 수 없음)

가장 짧은 string의 길이만큼 반복하면서 한글자씩 모두 동일한지 검토한다

모두 동일하지 않은 시점에서 리턴 

 

2. 내가 한 실수 / 고민

시간 복잡도를 크게 고려하지 않음

 

3. 핵심 아이디어

가장 짧은 문자열 기준으로 비교 

 

4. 시간 복잡도

O(n*m)

n: strs배열의 크기

m:  가장 짧은 string의 길이 

 

5. 다른 사람의 풀이

 

1)

function longestCommonPrefix(strs: string[]): string {
    if (!strs.length) return "";


    const sortedArray = strs.sort((a, b) => (a < b ? -1 : 1));

    for (let step = 0; step < sortedArray[0].length; step++) {
        if (sortedArray[0][step] !== sortedArray[sortedArray.length - 1][step]) {
            return sortedArray[0].substring(0, step);
        }

    }

    return sortedArray[0];
};

array를 알파벳순으로 비교하게되면, 배열의 맨 처음 단어와 맨 마지막단어만 비교하면 된다 ㄷㄷ 놀랍다!

 

function longestCommonPrefix(strs: string[]): string {
    let prefix = strs[0]
    
    if(prefix==="") return ""

    for (let i = 1; i<strs.length; i++) {
        const str = strs[i]

        //while is not a prefix
        while (str.startsWith(prefix)!==0) {
            prefix = prefix.substr(0, prefix.length-1)
            if(prefix === "") return ""
        }
    }
    return prefix
};

startsWith라는 prefix를 확인할 수 있는 함수가 있음!

prefix를 전체 문자열에서 한개씩 줄여가면서 검사하는 방법 

 

 

6. 다음에 다시 풀 수 있나?

음.. 그럴것 같음