Longest Common Prefix
1 min read

Longest Common Prefix

Given an array of strings, return the longest common prefix that is shared amongst all strings.
Note: you may assume all strings only contain lowercase alphabetical characters.

Ex: Given the following arrays...

["colorado", "color", "cold"], return "col"
["a", "b", "c"], return ""
["spot", "spotty", "spotted"], return "spot"

There are different approaches to this like Horizontal Scanning, Vertical Scanning , Binary Search

For the current solution i cose the Binary Search approach as that seemed more efficient at the time.

fun longestCommonPrefix(strs: Array<String>): String {
    if(strs.isNullOrEmpty()) return ""
        var minLen = Integer.MAX_VALUE
        
        for(str in strs) {
            minLen = Math.min(minLen, str.length)
        }
        var low = 1
        var high = minLen
        
        while(low <= high) {
            var middle = (low + high) / 2
            if(isCommonPrefix(strs, middle)){
                low = middle + 1
            } else {
                high = middle - 1
            }
        }
        return strs[0].substring(0,(low + high) / 2)
}

private fun isCommonPrefix(strs: Array<String>, len:Int): Boolean {
      var str = strs[0].substring(0,len)
       for(i in 1..strs.size-1) {
           if(!strs[i].startsWith(str)){
               return false
           }
       }
     return true
   }

Enjoying these posts? Subscribe for more