茂名专业网站建设,asp.net课程网站模板下载,制作企业网站的版式,艺术设计类网站优质博文#xff1a;IT-BLOG-CN
一、题目
编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀#xff0c;返回空字符串。
示例 1#xff1a; 输入#xff1a;strs [flower,flow,flight] 输出#xf…优质博文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(mlogn)其中m是字符串数组中的字符串的平均长度n是字符串的数量。空间复杂度主要取决于递归调用的层数层数最大为logn每层需要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(mnlogm)其中m是字符串数组中的字符串的最小长度n是字符串的数量。二分查找的迭代执行次数是O(logm)每次迭代最多需要比较mn个字符因此总时间复杂度是O(mnlogm)。 空间复杂度 O(1)。使用的额外空间复杂度为常数。
