题目
Write a function to find the longest common prefix string amongst an array of strings.
这是一道简单题。但是看了Editorial Solution。感觉自己的算法道路还是很长。
简单的思路
第一种、用第一个字符串去和第二个比，找到公共部分，循环操作和剩下的比。返回公共部分。
第二种、比较每个字符串的第一个字母，全部相同则比较下一个字母。直至出现不同为止。若数组长度为m，每个字符串长度为n这两种代码最坏情况花的时间是一致的，都是O(m*n)个人用了第二种。代码一
public class Solution { public String longestCommonPrefix3_2(String[] strs) { int N = strs.length; if (N == 0) return ""; // i 一个字符串的长度 // j 数组String[] 长度 // 比较每个字符串的公共部分 String prefix = strs[0]; int i = prefix.length(); for (int j = 0; j < N; j++) { while (strs[j].indexOf(prefix) != 0) { prefix = prefix.substring(0, i--); if (prefix.isEmpty()) return ""; } } return prefix; } } Point
s.indexOf(prefix)要考虑prefix是否为""的情况
代码二
public String longestCommonPrefix3(String[] strs) { int N=strs.length; if(N==0) return ""; // ith character 一个字符串中 第i个字母 // jth index String[]数组的下标 // 依次比较每个字符串的第i个字母 for(int i=0;i Point
这个if判断条件现在看来简单精炼，写的时候真是要了命了。主要是边界问题的判断。
首先，位置不能交换。得先判断第i个字母仍在这个字符串的范围内，然后才能根据这个位置i去找这个字母。
其次，位置i得超出边界才能中断返回。不能想着位置i到了边界，就直接返回。因为在这个位置i，其他字符串并没有遍历。因此要等遍历完，i超出边界再中断返回才可以。
二分法
讲真这个最坏情况应该是最慢的，不知道为什么测试结果却比前面两种要快。难道是平均较好？
public String longestCommonPrefix(String[] strs) { int N = strs.length; if (N == 0) return ""; int min=Integer.MAX_VALUE; for(String s:strs) min=Math.min(min,s.length()); int lo=1; int hi=min; while(lo<=hi){ int mid=(lo+hi)/2; if(isCommonPrefix(strs,mid)){ lo=mid+1; } else hi=mid-1; } return strs[0].substring(0, (lo+hi)/2); } public boolean isCommonPrefix(String[] strs,int len){ int N=strs.length; String prefix=strs[0].substring(0, len); for(String s:strs){ if(!s.startsWith(prefix)) return false; } return true; }