[LeetCode] Longest Common Prefix

https://leetcode.com/problems/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 if it is non-empty.

고민

딱! 보면 쉬워 보인다.
"아~ 공통으로 사용되는 prefix를 찾으면 되는거군?"
항상 난.. 이렇게 어리숙한 생각을 가지고 헤딩하면 뚝빼기가 깨지기 마련이지..ㅎ..

머리가 나쁘니 몸이 고생하지뭐 ㅎ👶🏻

일단 루프 돌려! 확인해야지!!!

해결

class Solution {
    fun longestCommonPrefix(strs: Array<String>): String {
        var firstStr = strs[0]
        for (i in 1 until strs.size) {
            while (strs[i].indexOf(firstStr) != 0) {
                firstStr = firstStr.substring(0, firstStr.length - 1)
                if (firstStr.isEmpty()) return ""
            }
        }
        return firstStr
    }
}

주어지는 배열에서 첫번째 요소를 기준을 잡고 확인했다.

두번째 요소부터 for 루프를 돌면서 해당 요소의 시작이 첫번째 요소로 시작하지 않는다면 마지막 요소부터 제거하는 방식을 사용했다.
제거를 함으로써 prefix 의 후보를 없애는 방식인것이다.

예제를 예를 들면 ["flower", "flow", "flight"] 에서 첫번째 요소 flower 가 기준!
두번째 요소 flow 가 비교 대상이 되는데, flower 는 flow 의 prefix 가 되지 않으니 필요없는 'er'를 하나씩 제거한다.
이제 세번째 요소 flight를 비교한다. flight 는 flow 의 prefix 가 되지 않으니 필요없는 'ight'가 하나씩 제거된다.
그래서 결과 값은 'fl'가 된다.

나로썬 이게 최선이었다.....

결과

우와 처음으로 박수 아이콘이 한번에 붙은 것 같다!!!!!!!!!!!!!

다른 분들은 어떻게 했지?

후기

class Solution {
    fun longestCommonPrefix(strs: Array<String>): String {
        var kal = strs[0].length
        for (i in 1 until strs.size){
            while(strs[i].length < kal|| strs[0].substring(0,kal) != strs[i].substring(0,kal)){
                kal -= 1
            }
        }
        return strs[0].substring(0,kal)
    }
}

0ms 걸린 코드이다. (0ms 도대체 어떻게...할...수..큼큼..)

나는 냅다 string 자체를 비교했는데 이분은 string 의 index 로 비교했다. (WOW..)
어차피 접두사(prefix)는 index 로 충분히 구할 수 있으니 이 방법도 상당히 효율적으로 보인다.

자 이제 뜯어보자.
비교 기준이 되는 첫번째 요소의 length 를 가지고 나머지 요소들의 length 를 비교한다.
첫번째 요소 외의 요소가 첫번째 요소보다 짧다면 비교 자체가 안되니 무조건적으로 줄여야하는게 맞다.
첫번째 요소의 length 와 비교 대상의 length 가 다르다면 동일한 length 까지 줄이는게 맞다.
그럼 결국 공통된 prefix 의 index 가 구해진다...........

정말.. 좋다..! String 보다는 Integer 가 더 가벼울테니 .... 하나 또 배워간다...