当前位置:   article > 正文

LeetCode力扣每日一题(Java):14、最长公共前缀_java leetcode最长公共前缀、

java leetcode最长公共前缀、

一、题目

二、解题思路

1、我的思路

乍一看我的代码量还是比较少,但是提交上去发现时间效率和空间效率都不占优势

讲讲我的思路:首先通过for循环找出数组中长度最短的字符串,并用min储存最短字符串的长度,最长公共前缀不可能比min更大。其次在通过双重循环逐个比较数组中字符串的每一位是否对应相等,若相等就往s中追加一个字母,若不相等则直接结束程序,返回s

  1. String s = "";
  2. int min = strs[0].length();
  3. for (int i = 1; i < strs.length; i++){
  4. if(strs[i].length() < min){
  5. min = strs[i].length();
  6. }
  7. }
  8. for (int j = 0; j < min; j++) {
  9. for (int i = 1; i < strs.length; i++) {
  10. if (strs[0].charAt(j) != strs[i].charAt(j)) {
  11. return s;
  12. }
  13. }
  14. s += strs[0].charAt(j);
  15. }
  16. return s;

2、官方题解

力扣提供了四种题解,我们一种一种来看(终于体会到一道算法题,一看一下午的感觉了)

方法一:横向扫描

  1. public String longestCommonPrefix(String[] strs) {
  2. if (strs == null || strs.length == 0) {
  3. return "";
  4. }
  5. String prefix = strs[0];
  6. int count = strs.length;
  7. for (int i = 1; i < count; i++) {
  8. prefix = longestCommonPrefix(prefix, strs[i]);
  9. if (prefix.length() == 0) {
  10. break;
  11. }
  12. }
  13. return prefix;
  14. }
  15. public String longestCommonPrefix(String str1, String str2) {
  16. int length = Math.min(str1.length(), str2.length());
  17. int index = 0;
  18. while (index < length && str1.charAt(index) == str2.charAt(index)) {
  19. index++;
  20. }
  21. return str1.substring(0, index);
  22. }

看完这段代码,脑袋里冒出两句话:层层套娃但是妙啊,可我也确实想不到啊

这种方法只能靠积累了,反正我是想不到的(而且我也解释不来,所以大家自己看吧)

方法二:纵向扫描

  1. public String longestCommonPrefix(String[] strs) {
  2. if (strs == null || strs.length == 0) {
  3. return "";
  4. }
  5. int length = strs[0].length();
  6. int count = strs.length;
  7. for (int i = 0; i < length; i++) {
  8. char c = strs[0].charAt(i);
  9. for (int j = 1; j < count; j++) {
  10. if (i == strs[j].length() || strs[j].charAt(i) != c) {
  11. return strs[0].substring(0, i);
  12. }
  13. }
  14. }
  15. return strs[0];
  16. }
  17. 作者:力扣官方题解
  18. 链接:https://leetcode.cn/problems/longest-common-prefix/
  19. 来源:力扣(LeetCode)
  20. 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

这种方法和我的思路有异曲同工之妙,但我的方法更复杂一些

其实我一开始写的代码和官方题解挺像的,下面是我一开始提交的代码

  1. class Solution {
  2. public String longestCommonPrefix(String[] strs) {
  3. String s = "";
  4. for (int j = 0; j < strs[0].length(); j++) {
  5. for (int i = 1; i < strs.length; i++) {
  6. if (strs[0].charAt(j) != strs[i].charAt(j)) {
  7. return s;
  8. }
  9. }
  10. s += strs[0].charAt(j);
  11. }
  12. return s;
  13. }
  14. }

但是我没有考虑到i == strs[j].length()的情况,所以提交的时候代码执行出错了,还是思维不够严谨导致的

方法三:分治

  1. class Solution {
  2. public String longestCommonPrefix(String[] strs) {
  3. if (strs == null || strs.length == 0) {
  4. return "";
  5. } else {
  6. return longestCommonPrefix(strs, 0, strs.length - 1);
  7. }
  8. }
  9. public String longestCommonPrefix(String[] strs, int start, int end) {
  10. if (start == end) {
  11. return strs[start];
  12. } else {
  13. int mid = (end - start) / 2 + start;
  14. String lcpLeft = longestCommonPrefix(strs, start, mid);
  15. String lcpRight = longestCommonPrefix(strs, mid + 1, end);
  16. return commonPrefix(lcpLeft, lcpRight);
  17. }
  18. }
  19. public String commonPrefix(String lcpLeft, String lcpRight) {
  20. int minLength = Math.min(lcpLeft.length(), lcpRight.length());
  21. for (int i = 0; i < minLength; i++) {
  22. if (lcpLeft.charAt(i) != lcpRight.charAt(i)) {
  23. return lcpLeft.substring(0, i);
  24. }
  25. }
  26. return lcpLeft.substring(0, minLength);
  27. }
  28. }
  29. 作者:力扣官方题解
  30. 链接:https://leetcode.cn/problems/longest-common-prefix/
  31. 来源:力扣(LeetCode)
  32. 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

方法四:二分查找

  1. class Solution {
  2. public String longestCommonPrefix(String[] strs) {
  3. if (strs == null || strs.length == 0) {
  4. return "";
  5. }
  6. int minLength = Integer.MAX_VALUE;
  7. for (String str : strs) {
  8. minLength = Math.min(minLength, str.length());
  9. }
  10. int low = 0, high = minLength;
  11. while (low < high) {
  12. int mid = (high - low + 1) / 2 + low;
  13. if (isCommonPrefix(strs, mid)) {
  14. low = mid;
  15. } else {
  16. high = mid - 1;
  17. }
  18. }
  19. return strs[0].substring(0, low);
  20. }
  21. public boolean isCommonPrefix(String[] strs, int length) {
  22. String str0 = strs[0].substring(0, length);
  23. int count = strs.length;
  24. for (int i = 1; i < count; i++) {
  25. String str = strs[i];
  26. for (int j = 0; j < length; j++) {
  27. if (str0.charAt(j) != str.charAt(j)) {
  28. return false;
  29. }
  30. }
  31. }
  32. return true;
  33. }
  34. }
  35. 作者:力扣官方题解
  36. 链接:https://leetcode.cn/problems/longest-common-prefix/
  37. 来源:力扣(LeetCode)
  38. 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

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

闽ICP备14008679号