leetcode14. 最长公共前缀

14. 最长公共前缀

注意，这是公共前缀，是从字符串第一个符号开始的，不是子串。

法一：横向扫描。自己先写的。

class Solution {public String longestCommonPrefix(String[] strs) {int len = strs.length;if(len == 1)  return strs[0];String commonPre = longestCommon(strs[0],strs[1]);for(int i = 2;i < len;++i){if(commonPre.equals(""))  return "";commonPre = longestCommon(commonPre,strs[i]);}return commonPre;}public String longestCommon(String s1,String s2) {int m = s1.length(),n = s2.length(),i = 0;if(m == 0 || n == 0)  return "";for(;i < m && i < n;++i){if(s1.charAt(i) != s2.charAt(i))  break;}return s1.substring(0,i);}
}

法二：纵向扫描，更推荐。

class Solution {public String longestCommonPrefix(String[] strs) {if (strs == null || strs.length == 0)  return "";int length = strs[0].length();int count = strs.length;// 纵向扫描：逐个字符位置进行比较for (int i = 0; i < length; i++) {// 获取第一个字符串在第i位置的字符，作为比较标准char c = strs[0].charAt(i);// 遍历数组中其他字符串，与第一个字符串的同一位置进行比较for (int j = 1; j < count; j++) {// 终止条件1：当前字符串长度不足，已到达其末尾// 终止条件2：当前字符串在第i位置的字符与标准字符不匹配if (i == strs[j].length() || strs[j].charAt(i) != c) {// 返回从开头到不匹配位置前一位的子字符串return strs[0].substring(0, i);}}}// 如果所有字符串都完全匹配（第一个字符串是最短且为公共前缀）return strs[0];}
}

 这两个方法时间复杂度O(mn)，已经是时间空间最优。本题还有其他两种方法，不是双优，这里就不展示了。