[LeetCode/Kotlin]Easy - 14. Longest Common Prefix

Longest Common Prefix - LeetCode

문제

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.

풀이

나의 풀이법

풀이 접근 과정

내가 어렵게 접근했던 이유는 어느 위치건 상관 없는 공통의 단어를 뽑아내는 줄 알았다.

예를 들어 strs = ["reflower","flow","flight"] 인 경우 결과값은 fl 이라고 생각했다.

그렇게 구현했더니 결과값이 틀리게 나왔다. 위치가 중요한가보다.

그렇다. 이건 가장 긴 단어를 고르는게 아니라 가장 긴 “접두사”를 찾아내는 문제였다 …..

class Solution {
    fun longestCommonPrefix(strs: Array<String>): String {
        if (strs.size == 1) return strs[0]
        
        var answer = ""
        var common = ""

        var prefixIndex = Array(strs.size+1) { -1 }

        strs[0].forEach {
            for (i in 1 until strs.size) {
                val commonIndex = checkCommonWord(strs[i], it, prefixIndex[i])

                if (commonIndex == -1) {
                    prefixIndex = Array(strs.size+1) { -1 }
                    if (answer.length < common.length) {
                        answer = common
                    }
                    common = ""
                    return@forEach
                }
            }

            common += it
        }

        return answer
    }

    private fun checkCommonWord(word: String, prefix: Char, index: Int): Int {
        if (index == -1) {
            word.forEachIndexed { idx, s ->
                if (prefix == s) return idx
            }
        } else {
            if (word[index+1] == prefix) return index+1
        }

        return -1
    }
}

아쉬우니 가장 긴 단어를 찾아내는 소스 코드도 추가하구….

이거 소스 짠다고 머리 겁나 굴렸는데 ㅋㅋㅋㅋㅋ 짜증나 !!!

문제를 제대로 파악 안한 내 탓이쥐… 영어 공부해야겠다 ㅜ

최종 소스코드

class Solution {
    fun longestCommonPrefix(strs: Array<String>): String {
        if (strs.size == 1) return strs[0]
        
        var answer = ""

        strs[0].forEachIndexed { idx, s ->
            for (i in 1 until strs.size) {
                if (strs[i].length <= idx || strs[i][idx] != s) return answer
            }
            answer += s
        }

        return answer
    }
}

1. strs의 개수가 1개 밖에 없으면 0번째 값을 바로 리턴한다.
2. strs[0]을 기준으로 반복문을 돌린다. (공통 접두사 체크를 위해)
3. 만약 strs[i][index]의 문자들이 strs[0][index]와 같으면 answer에 strs[0][index]를 덧붙인다.
4. 만약 strs[i][index]의 문자가 strs[0][index]와 다르면 지금까지 만들어진 answer를 리턴한다.