14. 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: 
["flower","flow","flight"]

Output:
 "fl"

Example 2:

Input: 
["dog","racecar","car"]

Output:
 ""

Explanation:
 There is no common prefix among the input strings.

Note:

All given inputs are in lowercase letters a-z.

Solution

(1) Java

This is horizontal scan solution. The time complexity is O(s), and space complexity is O(1)

public String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0) {
            return "";
        }
        String prefix = strs[0];
        for (int i = 1; i < strs.length; i++) {
            for (int j = 0; j < prefix.length(); j++) {
                if (j >= strs[i].length() || prefix.charAt(j) != strs[i].charAt(j)) {
                    prefix = prefix.substring(0, j);
                    break;
                }
            }
        }
        return prefix;
    }

(2) Python

This is vertical scan solution. The same complexity.

class Solution(object):
    def longestCommonPrefix(self, strs):
        """
        :type strs: List[str]
        :rtype: str
        """
        if not strs:
            return ""
        prefix = strs[0]
        for i in range(len(prefix)):
            c = prefix[i]
            for j in range(1, len(strs)):
                if i == len(strs[j]) or c != strs[j][i]:
                    return prefix[:i]
        return prefix

(3) Scala

object Solution {
    def longestCommonPrefix(strs: Array[String]): String = {
        if (strs == null || strs.length == 0) {
            return ""
        }
        var prefix = strs(0)
        for (i <- 1 until strs.length) {
            var break = false;
            var j = 0
            while( j < prefix.length() && !break) {
                if (j >= strs(i).length() || prefix(j) != strs(i)(j)) {
                    prefix = prefix.substring(0, j)
                    break = true;
                }
                j = j+1
            }
        }
        return prefix
    }
}