leetcode: 14. Longest Common Prefix

문제링크

풀이1

• 내장함수 commonPrefixWith 사용

class Solution {
    fun longestCommonPrefix(strs: Array<String>): String {
        var prefix = strs[0]
        for (i in 1 until strs.size) {
            prefix = strs[i].commonPrefixWith(prefix)
        }
        return prefix
    }
}

풀이2

• indexOf 사용

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

풀이3

• Divide & Conquer

import kotlin.math.min

class Solution {
    fun longestCommonPrefix(strs: Array<String>): String {
        val size = strs.size
        if (size == 0) return ""
        return longestCommonPrefix(strs, 0, size - 1)
    }
    
    private fun longestCommonPrefix(strs: Array<String>, start: Int, end: Int): String {
        if (start == end) return strs[start]
        val mid = (start + end) / 2
        val leftCommonPrefix = longestCommonPrefix(strs, start, mid)
        val rightCommonPrefix = longestCommonPrefix(strs, mid + 1, end)
        return commonPrefix(leftCommonPrefix, rightCommonPrefix)
    }
    
    private fun commonPrefix(s1: String, s2: String): String {
        val minLength = min(s1.length, s2.length)
        for (i in 0 until minLength) {
            if (s1[i] != s2[i]) return s1.substring(0, i)
        }   
        return s1.substring(0, minLength)
    }
}