[leetcode] 14. Longest Common Prefix - 자바스크립트 0607

문제

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

제한사항

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

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

Longest Common Prefix - LeetCode

정렬에 있는 문자를 앞글자부터 비교해서, 가장 긴 공통의 글자가 있는지를 찾는 문제이다.

문제를 해결하기 위해서는 for문을 두번사용해야 한다. 하지만, 일반적으로 문제를 사용하는 방법대로 쓰는 방법의 반대방향인

    for (let i = 0; i < arr[0].length; i++) {
        for (let j = 0; j < arr.length; j++) {
        }
 }

arr[x][y]가 있다고 하면, y위치를 먼저 루프를 시킨뒤 x를 기준으로 루프를 시킨다. 이 순서대로 루프를 시켜야, 각 글자마다 문자가 일치하는지 확인할 수 있다. 테스트 케이스를 ["flower", "flow", "flight"] 라고 가정을 하면,

"flow"[0] ==="f", "flight"[0]==="f" 둘다 f로 시작하기에, answer = f

"flow"[1] ==="l", "flight"[1]==="l" 둘다 두번째 글자가 l이기에, answer = fl

"flow"[2] !=="f", "flight"[2]!=="f" 세번 째 글자는 다르기에, 여기서 return answer = fl을 하면된다. 

arr.length중 한개라도 성립을 안하면을 찾아야 하기때문에

    for (let i = 0; i < arr[0].length; i++) {
        let isCorrect = true
        for (let j = 0; j < arr.length; j++) {
            if (arr[j][i] !== arr[0][i]) {
                isCorrect = false
            }
        }
        if (!isCorrect) {
            return answer
        } else {
            answer += arr[0][i]
        }
    }

isCorrect를 통하여 체크를 하는 것이 좋다.

다음은 전체 문제풀이이다.

function solution(arr) {
    let answer = ""
    for (let i = 0; i < arr[0].length; i++) {
        let isCorrect = true
        for (let j = 0; j < arr.length; j++) {
            if (arr[j][i] !== arr[0][i]) {
                isCorrect = false
            }
        }
        if (!isCorrect) {
            return answer
        } else {
            answer += arr[0][i]
        }
    }
    return answer
}

만약에 메모리를 조금 더 줄이고 싶다면

function solution(arr) {
    let answer = ""
    if (arr.length === 1) { return arr[0] }
    for (let i = 0; i < arr[0].length; i++) {
        let isCorrect = true
        for (let j = 1; j < arr.length; j++) {
            if (arr[j][i] !== arr[0][i]) {
                isCorrect = false
            }
        }
        if (!isCorrect) {
            return answer
        } else {
            answer += arr[0][i]
        }
    }
    return answer
}

아래와 같은 풀이로 풀이할 수 있다