O(n) solution in Scala


#1
def getLongestPrefix(str1: String, str2: String): String = {
    
    val sb = new StringBuilder()
    var i = 0
    while(i < str1.length && i < str2.length && str1.charAt(i) == str2.charAt(i)){
        sb.append(str1.charAt(i))
        i += 1
    }
    return sb.toString()
}

def longestCommonPrefix(A: Array[String]): String  = {
    
    if(A.length == 0)
        return ""
    
    if(A.length == 1)
        return A(0)
    
    var i = 0
    var longestPrefix: Option[String] = None
    while(i < A.length - 1){
        val prefix = getLongestPrefix(A(i), A(i + 1))
        if(prefix.length == 0)
            return ""
        if(longestPrefix == None || prefix.length < longestPrefix.get.length){
            longestPrefix = Some(prefix)
        }
        i += 1
    }
    return longestPrefix.getOrElse("")
}

#2

Definitely NOT O(N).

For each element in the Array A you do a StringBuilder and toString()
Although creating a new String at each loop is useless, that brings the complexity up to O(N * M)
with M being the length (or max length in worst case) of your strings