05 August 2008
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:
1
2
Input: ["flower","flow","flight"]
Output: "fl"
Example 2:
1
2
3
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’.
求一个字符串数组的最长的共同前缀，字符串都是小写字母，这个只能把所有单词排成纵列挨个查了，如果查找的过程中某一个字符串没有了，或者某个字符串的字符不同，那就直接上一轮保存的最长公共前缀。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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);//不包括i位置的字符
}
}
}
return strs[0];//如果都遍历结束了还没有return，那第一个字符串就是最短的字符串（之一），本省就是最长前缀
}
}
设定公共长度是第一个元素的长度
多利用已经计算过的结果来为新的计算服务
如：假设数组元素有多个
第一个和第二个元素已经比较过
那么第二个和第三个进行比较时，就受到了第一个和第二个元素比较结果的约束
Math.min(第二个和第三个元素的公共长度，第一个元素和第二个元素公共长度) 在比较时，只需要找到最小的len即可，无需全部遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
// 思路：一直比较得到每一次的最小公共长度
public String longestCommonPrefix(String[] str) {
int len = str[0].length();
for (int i = 1; i < str.length; i++) {
len = Math.min(len, judge(str[i - 1], str[i], len));
if (len == 0) {
return "";
}
}
return str[0].substring(0, len);
}
public int judge(String s1, String s2, int len) {
int i = 0;
for (; i < s1.length() && i < s2.length() && i < len; i++) {
if (s1.charAt(i) != s2.charAt(i)) {
break;
}
}
return Math.min(len, i);
}
}