题目
最长公共前缀
给k个字符串，求出他们的最长公共前缀(LCP)
样例
在 "ABCD" "ABEF" 和 "ACEF" 中, LCP 为 "A"
在 "ABCDEFG", "ABCEFG", "ABCEFA" 中, LCP 为 "ABC"
解题
思路：
1.找到最短的字符串，求出长度shortest
2.设最短公共前缀是shortest
3.遍历所有字符串，比较长度是shortest的前缀是否相同，相同就是答案
3.不相同shortest-=1 重复 2 、3 步
Java
public class Solution {
/**
* @param strs: A list of strings
* @return: The longest common prefix
*/
public String longestCommonPrefix(String[] strs) {
// write your code here
HashMap<Character,Integer> map= new HashMap<Character,Integer>();
if(strs.length ==0)
return "";
int len = strs.length;
int shortest = Integer.MAX_VALUE;
for(int i=0;i<len;i++){
int tmplen = strs[i].length();
shortest = Math.min(shortest,tmplen);
}
int i =0;
while(shortest>0){
for( i=0;i<len-1;i++){
String str1 = strs[i].substring(0,shortest);
String str2 = strs[i+1].substring(0,shortest);
if( str1.equals(str2))
continue;
else
break;
}
if(i==len-1)
break;
else
shortest--;
}
return strs[0].substring(0,shortest);
}
}
Java Code
既然可以倒着走，也可以正着走
public class Solution {
/**
* @param strs: A list of strings
* @return: The longest common prefix
*/
public String longestCommonPrefix(String[] strs) {
// write your code here
if(strs.length ==0)
return "";
if(strs.length == 1)
return strs[0];
int len = strs.length;
int shortest = 1;
boolean flag = false;
int i =0;
while(!flag){
for( i=0;i<len-1;i++){
if(strs[i].length() < shortest|| strs[i+1].length() < shortest){
flag = true;
break;
}
String str1 = strs[i].substring(0,shortest);
String str2 = strs[i+1].substring(0,shortest);
if( str1.equals(str2))
continue;
else
break;
}
if(i==len-1)
shortest++;
else{
flag= true;
}
}
return strs[0].substring(0,shortest-1);
}
}
Java Code
正着走就没有比较字符串，直接比较对应字符是否相等就好了
public class Solution {
/**
* @param strs: A list of strings
* @return: The longest common prefix
*/
public String longestCommonPrefix(String[] strs) {
// write your code here
if(strs.length ==0)
return "";
if(strs.length == 1)
return strs[0];
int len = strs.length;
int shortest = 0;
boolean flag = false;
int i =0;
while(!flag){
for( i=0;i<len-1;i++){
if(strs[i].length() <= shortest|| strs[i+1].length() <= shortest){
flag = true;
break;
}
char ch1 = strs[i].charAt(shortest);
char ch2 = strs[i+1].charAt(shortest);
if( ch1== ch2)
continue;
else
break;
}
if(i==len-1)
shortest++;
else{
flag= true;
}
}
return strs[0].substring(0,shortest);
}
}
Java Code
可能会发现三个返回结果为什么不一样？
1.逆着找，取子串的方式是 substring(start,end) 取得是从start 到 end -1 位置内的字符，这里的shortest就相当于end 在最后比较结束的时候 shortest 是当前比较结束的位置，这个end位置内的前缀都一样
所以返回的是substring(0,shortest) 取得字符是：0 到shortest -1的部分
2.正着找，跳出循环的是 第一个不满足条件的shortest ，取子串的方式也是 substring(start,end) 需要进行shortest - 1
3.比较字符，跳出循环的shortest是最长子串的后一个位置，可以直接用substring（0,shortest） 返回结果的
