Longest Common Prefix

Write a function to find the longest common prefix string amongst an array of strings.

Understand the problem:
The question asks for finding the longest common prefix (LCP) string among an array of strings. We can take an example to illustrate this problem. For the array of strings
a
bc
cd
The LCP string is empty as there is no common prefix at all.

For the array of strings
a
ab
abc
The LCP string is "a" since a is the longest common prefix string

For an array of strings
abc
abd
abfghi
The LCP string is "ab" since it is the longest common prefix string.

Solution:
Based on the analysis above, we can come up a solution. We compare the character with the same index for each of the string. If the same, we go to the next. There are two termination conditions:
a. the LCP is the shortest string, as in the example 2. 
b. the LCP is the substring of a string, we continue until we found the character is different. 

Code (Java):

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14

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

Discussion:
The time complexity of this solution is O(m * n), where m is the length of the LCP string, n is the number of strings in the array.

Summary:
It is not a very difficult question, but requires careful implementation. Note the outer loop, where i < strs[0].length(). Think about why we choose to use strs[0].length() ? Actually what we wanna find is the LCP string. So if strs[0] itself is the LCP string, it is fine. If strs[0] is not, we have other conditions inside of the loop to terminate the loop. How about we choose strs[1]? It is basically correct, however be careful about the size of the array, which has only one element. So we must change the code slightly like this:

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

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

Update on 9/28/15:

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27

public class Solution {     public String longestCommonPrefix(String[] strs) {         if (strs == null || strs.length == 0) {             return "";         }                   StringBuffer sb = new StringBuffer();                   for (int i = 0; i < strs[0].length(); i++) {             char curr = strs[0].charAt(i);             int j = 1;             for (j = 1; j < strs.length; j++) {                 String str = strs[j];                 if (str == null || str.length() == 0 || i >= str.length() || str.charAt(i) != curr) {                     break;                 }             }             if (j == strs.length) {                 sb.append(curr);             } else {                 break;             }         }                   return sb.toString();     } }