当前位置:   article > 正文

LeetCode第十四题:最长公共前缀(java)_最长公共前缀java

最长公共前缀java

题目:最长公共前缀

编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀,返回空字符串 ""

示例:

  1. 输入:strs = ["flower","flow","flight"]
  2. 输出:"fl"
  3. 输入:strs = ["dog","racecar","car"]
  4. 输出:""
  5. 解释:输入不存在公共前缀。

题目解读:

题目比较简单,对字符串进行操作。

我当时做时候第一想法是,循环比较每个元素的字符是否相等,直到不相等退出循环。

方法一:纵向扫描

以第一个元素为准,循环比较每个元素相同位置的字符是否相等。

不相等则退出循环,最长公共长缀为substring(0,i)。

注意:substring左闭右开,公共部分为0 到 i-1位置的元素。

其中 被比较的元素长度 小于 第一个元素长度  时 就会出现 取不到 第 i 个元素,此时被比较的字符串长度 等于 i 。也就是 strs[j].length() == i 这个条件。最长公共长缀 最长也只能是最短元素的长度。

这种思路比较容易想到。

  1. //纵向扫描
  2. public static String longestCommonPrefix1(String[] strs) {
  3. if (strs.length == 0 || strs == null) {
  4. return "";
  5. }
  6. //第一个字符串的长度
  7. int len = strs[0].length();
  8. //数组里有几个元素
  9. int legth = strs.length;
  10. for (int i = 0; i < len; i++) {
  11. for (int j = 1; j < legth; j++) {
  12. //strs[j].length() == i 表示当前字符串的长度小于strs[0]的长度
  13. if (strs[j].length() == i || strs[j].charAt(i) != strs[0].charAt(i)) {
  14. return strs[0].substring(0, i);
  15. }
  16. }
  17. }
  18. return strs[0];
  19. }

 官方的图很清晰明了,就不自己画了

方法二:横向扫描

 第一二组元素比较得出公共前缀,得到的公共前缀再依次和后面的元素比较,同时更新公共前缀。可以遍历完各个元素,得到的就是最长公共前缀。若未遍历完,公共前缀已经是空,则前面的元素已经没有公共前缀,也不需要后面的循环,直接退出循环即可。

  1. //横向扫描
  2. public static String longestCommonPrefix2(String[] strs) {
  3. if (strs.length == 0 || strs == null) {
  4. return "";
  5. }
  6. int len = strs.length;
  7. //注意prefix 不能为空字符串
  8. String prefix = strs[0];
  9. for (int i = 0; i < len - 1; i++) {
  10. prefix = maxPrefix(prefix, strs[i + 1]);
  11. //公共最长前缀为0,无公共前缀
  12. if (prefix.length() == 0) {
  13. break;
  14. }
  15. }
  16. return prefix;
  17. }
  18. //最长前缀
  19. public static String maxPrefix(String str1, String str2) {
  20. int length = Math.min(str1.length(), str2.length());
  21. int index = 0;
  22. while (index < length && str1.charAt(index) == str2.charAt(index) ) {
  23. index++;
  24. }
  25. // for (int i = 0; i < length; i++) {
  26. // if (str1.charAt(i) == str2.charAt(i)) {
  27. // index++;
  28. // } else {
  29. // break;
  30. // }
  31. // }
  32. return str1.substring(0, index);
  33. }

 这种思路我没想到,但是不难理解。得到公共前缀,一次和每个元素比较,更新公共前缀。

方法三:分而治之

类似归并排序的思路

把整个数组分为左右两部分,左边的最长公共前缀 与 右边的最长公共前缀 的 最长公共前缀 就是 整个数组的最长公共前缀。左边的最长公共前缀可以再分为左右两部分,同上操作。直至分为一个元素,他自己就是最长公共长缀。再算它和另一部分的最长公共前缀,往上不断合并。

思想有点类似

  1. public static String longestCommonPrefix(String[] strs) {
  2. if (strs.length == 0 || strs == null) {
  3. return "";
  4. }
  5. return longestCommonPrefix(strs,0,strs.length-1);
  6. }
  7. public static String longestCommonPrefix(String[] strs, int start, int end) {
  8. if (start == end) {
  9. return strs[start];
  10. }
  11. //mid这么计算可以防止溢出,舍位
  12. int mid = (end - start) / 2 + start;
  13. //左边最长公共长缀
  14. String left=longestCommonPrefix3(strs,start,mid);
  15. //右边最长公共长缀
  16. String right=longestCommonPrefix3(strs,mid+1,end);
  17. //计算最长前缀
  18. return maxPrefix(left,right);
  19. }
  20. //最长前缀
  21. public static String maxPrefix(String str1, String str2) {
  22. int length = Math.min(str1.length(), str2.length());
  23. int index = 0;
  24. while (index < length && str1.charAt(index) == str2.charAt(index) ) {
  25. index++;
  26. }
  27. return str1.substring(0, index);
  28. }

 把问题不断分解成子问题,解决最小的子问题,在合并。最小子问题的循环结束条件要找到。感觉很像递归。

方法四:二分法

这种方法我没自己敲,就简单看了一下。用二分法,找到最长公共前缀的尾索引是多少。不断缩小所查找的范围。

  1. public String longestCommonPrefix(String[] strs) {
  2. if (strs == null || strs.length == 0) {
  3. return "";
  4. }
  5. int minLength = Integer.MAX_VALUE;
  6. for (String str : strs) {
  7. minLength = Math.min(minLength, str.length());
  8. }
  9. int low = 0, high = minLength;
  10. while (low < high) {
  11. int mid = (high - low + 1) / 2 + low;
  12. //是公共前缀则最长公共前缀的 尾索引 一定在mid之后
  13. if (isCommonPrefix(strs, mid)) {
  14. low = mid;
  15. } else {
  16. //不是公共前缀则最长公共前缀的 尾索引 一定在mid之前
  17. high = mid - 1;
  18. }
  19. }
  20. return strs[0].substring(0, low);
  21. }
  22. //判断是否是公共长缀
  23. public boolean isCommonPrefix(String[] strs, int length) {
  24. String str0 = strs[0].substring(0, length);
  25. int count = strs.length;
  26. for (int i = 1; i < count; i++) {
  27. String str = strs[i];
  28. for (int j = 0; j < length; j++) {
  29. if (str0.charAt(j) != str.charAt(j)) {
  30. return false;
  31. }
  32. }
  33. }
  34. return true;
  35. }

总结: 

第一种思路很容易想到,但是没想到可以用分治和二分法解决。

复习一下各种查找算法和排序算法

int mid = (end - start) / 2 + start; 这么计算中间位置,可以有效防止溢出,很常用。

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/凡人多烦事01/article/detail/727654
推荐阅读
相关标签
  

闽ICP备14008679号