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
}