Write a function to find the longest common prefix string amongst an array of strings.
（1）求最长公共前缀，可以把它和动态规划的最长公共子序列放到一起思考，s1,s2,,,sn的公共前缀一定是s1，s2，s3,s4公共前缀的一部分，一定是s1,s2的公共前缀的一部分. s1和s2的公共前缀：s1:helloworld 如果s2前缀s1则s1为公共前缀，否则s1长度缩短，再重复判断。
public String longestCommonPrefix(String[] strs){ if(strs.length==0) return ""; int length=strs.length; String com=strs[0]; for(int i=1;i<length;i++){ while(strs[i].indexOf(com)!=0){ com=com.substring(0, com.length()-1); // System.out.println(com); if(com.isEmpty()) return ""; } } System.out.println(com); return com; } （2）纵向考虑：如果按照方法1考虑，时间复杂度为O（S ），S为所有字符和，如果当s1很长sn很短时，不够高效，所以纵向考虑。纵向考虑注意要先判断串的长度大小（避免越界 ），再判断两串所选字符是否相同；
public String longestCommonPrefix2(String[] strs){ if(strs==null||strs.length==0) return ""; for(int i=0;i<strs[0].length();i++){ char c=strs[0].charAt(i); for(int j=1;j<strs.length ;j++){ if(i==strs[j].length()||strs[j].charAt(i)!=c){ //注意先判断i 和串长大小，再去判断两个字符是否相等 return strs[0].substring(0,i); } } } return strs[0]; }
