BiruLyu
5/24/2017 - 7:04 PM

## 14. Longest Common Prefix(#1 Sort).java

``````"""
Write a function to find the longest common prefix string amongst an array of strings.
"""
class Solution(object):
def longestCommonPrefix(self, strs):
"""
:type strs: List[str]
:rtype: str
"""

res = '';
j = 0;

if not strs:
return '';

length = len(min(strs)); ## waste some time

while(j < length):
temp = res;
res += strs[0][j];
for i in range(1,len(strs)):
if strs[i][j] != res[-1]:
return temp;
j += 1;

return res;

"""
"""
class Solution(object):
def longestCommonPrefix(self, strs):
"""
:type strs: List[str]
:rtype: str
"""

res = '';
j = 0;

if not strs:
return '';

while(1):
temp = res;
for i in range(0,len(strs)):
if j >= len(strs[i]) or (i > 0 and strs[i][j] != strs[i-1][j]):
return res;
res += strs[0][j];
j += 1;

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

/*

[]
["abc"]
["ab","abc","abc","abdc"]
["ab"]
["a","b"]
["aa","a"]

*/``````
``````class Solution {
public String longestCommonPrefix(String[] strs) {
if (strs == null || strs.length < 1) return "";
StringBuilder res = new StringBuilder();
Arrays.sort(strs);
char[] a = strs[0].toCharArray();
char[] b = strs[strs.length - 1].toCharArray();
for (int i = 0; i < a.length && i < b.length; i++) {
if (a[i] == b[i]) {
res.append(a[i]);
} else {
return res.toString();
}
}
return res.toString();
}
}``````