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.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/