# 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`.

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