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 lettersa-z.

Analysis

For multiple string comparison, what will be the fastest way to fail. It's intuitive to think of finding the shortest string first. And in worst case, it would involve n equal strings with length m and the algorithm performs S = m*n character comparisons. In best case it would be n * minLen, where minLen is the length of shortest string in the array.

Other approaches, like divide and conquer, binary search, building trie, see:

https://leetcode.com/articles/longest-common-prefix/

Solution

Two pass, one pass to get shortest string length, second to check common prefix

class Solution {
    public String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0) {
            return "";
        }

        StringBuilder sb = new StringBuilder();

        int shortest = Integer.MAX_VALUE;

        for (String str : strs) {
            shortest = Math.min(shortest, str.length());
        }

        for (int i = 0; i < shortest; i++) {
            char curr = strs[0].charAt(i);
            for (String str : strs) {
                if (str.charAt(i) != curr) {
                    return sb.toString();
                }
            }
            sb.append(curr);
        }
        return sb.toString();
    }
}

Reference

https://leetcode.com/articles/longest-common-prefix/