最长公共前缀[简单]

优质博文：IT-BLOG-CN

一、题目

编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀，返回空字符串""。

示例 1：
输入：strs = ["flower","flow","flight"]
输出：fl

示例 2：
输入：strs = ["dog","racecar","car"]
输出：“”
解释：输入不存在公共前缀。

1 <= strs.length <= 200
0 <= strs[i].length <= 200
strs[i]仅由小写英文字母组成

二、代码

【1】横向比较： 依次遍历字符串数组中的每个字符串，对于每个遍历到的字符串，更新最长公共前缀prex，当遍历完所有的字符串以后，即可得到字符串数组中的最长公共前缀。

class Solution {public String longestCommonPrefix(String[] strs) {// 思想：横向比较，数组中的数组暴力比较if (strs == null || strs.length == 0) {return "";}// 获取第一个元素作为基础数据进行比较，如果有比它更短的数据，可以return退出循环String prex = strs[0];for (int i = 1; i < strs.length; i++) {// 获取最小的长度int len = Math.min(prex.length(), strs[i].length());// 创建一个递增的下标int index = 0;while (index < len) {if (prex.charAt(index) != strs[i].charAt(index)) {break;}index++;}// 如果前缀是0可以直接退出if (index == 0) {return "";}prex = prex.substring(0,index);}return prex;}
}

时间复杂度： O(mn)其中m是字符串数组中的字符串的平均长度，n是字符串的数量。最坏情况下，字符串数组中的每个字符串的每个字符都会被比较一次。
空间复杂度： O(1)使用的额外空间复杂度为常数。

【2】纵向比较： 横向比较，依次遍历每个字符串，更新最长公共前缀。另一种方法是纵向比较。纵向扫描时，从前往后遍历所有字符串的每一列，比较相同列上的字符是否相同，如果相同则继续对下一列进行比较，如果不相同则当前列不再属于公共前缀，当前列之前的部分为最长公共前缀。直接返回即可。

class Solution {public String longestCommonPrefix(String[] strs) {if (strs == null || strs.length == 0) {return "";}// 思想：纵向比较：以strs[0]作为比较基本，循环依次取Char与其它元素进行比较，不相同直接退出即可。String prex = strs[0];for (int i = 0; i < prex.length(); i++) {// 获取比较的元素char p = prex.charAt(i);// 遍历其它元素，但是其它元素可能并没有第一个元素长，可以先比较长度for (int j = 1; j < strs.length; j++) {if (i == strs[j].length() || strs[j].charAt(i) != p) {return prex.substring(0,i);}}}return prex;}
}

时间复杂度： O(mn)其中m是字符串数组中的字符串的平均长度，n是字符串的数量。最坏情况下，字符串数组中的每个字符串的每个字符都会被比较一次。
空间复杂度： O(1)使用的额外空间复杂度为常数。

【3】分治思想： 使用归并排序的思想，先将strs拆分成个体，在通过治的思想，将相邻元素进行合并处理。

class Solution {public String longestCommonPrefix(String[] strs) {if (strs == null || strs.length == 0) {return "";}// 思想：采用分治思想，先将strs拆分为一个个单体，在进行两两合并比较即可return partition(strs, 0, strs.length - 1);}// 拆分方法public String partition(String[] strs, int start, int end) {// 递归退出条件if (start == end) {return strs[start];}int mid = (end - start) / 2 + start;String left = partition(strs, start, mid);String right = partition(strs, mid + 1, end);// 合并return merge(left, right);} // 合并方法public String merge(String left, String right) {int minLen = Math.min(left.length(), right.length());for (int i = 0; i < minLen; i++) {if (left.charAt(i) != right.charAt(i)) {return left.substring(0,i);}}return left.substring(0, minLen);}
}

时间复杂度： O(mn)其中m是字符串数组中的字符串的平均长度，n是字符串的数量。时间复杂度的递推式是T(n)=2⋅T(n/2)+O(m)，通过计算可得T(n)=O(mn)。
空间复杂度： O(mlog⁡n)，其中m是字符串数组中的字符串的平均长度，n是字符串的数量。空间复杂度主要取决于递归调用的层数，层数最大为log⁡n，每层需要m的空间存储返回结果。

【4】二分查找法： 最长公共前缀的长度不会超过字符串数组中的最短字符串的长度。用minLen表示字符串数组中的最短字符串的长度，则可以在[0,minLength]的范围内通过二分查找得到最长公共前缀的长度。每次取查找范围的中间值mid，判断每个字符串的长度为mid的前缀是否相同，如果相同则最长公共前缀的长度一定大于或等于mid，如果不相同则最长公共前缀的长度一定小于mid，通过上述方式将查找范围缩小一半，直到得到最长公共前缀的长度。

class Solution {public String longestCommonPrefix(String[] strs) {if (strs == null || strs.length == 0) {return "";}int minLength = Integer.MAX_VALUE;for (String str : strs) {minLength = Math.min(minLength, str.length());}int low = 0, high = minLength;while (low < high) {int mid = (high - low + 1) / 2 + low;if (isCommonPrefix(strs, mid)) {low = mid;} else {high = mid - 1;}}return strs[0].substring(0, low);}public boolean isCommonPrefix(String[] strs, int length) {String str0 = strs[0].substring(0, length);int count = strs.length;for (int i = 1; i < count; i++) {String str = strs[i];for (int j = 0; j < length; j++) {if (str0.charAt(j) != str.charAt(j)) {return false;}}}return true;}
}

时间复杂度： O(mnlog⁡m)，其中m是字符串数组中的字符串的最小长度，n是字符串的数量。二分查找的迭代执行次数是O(log⁡m)，每次迭代最多需要比较mn个字符，因此总时间复杂度是O(mnlog⁡m)。
空间复杂度： O(1)。使用的额外空间复杂度为常数。