纵向扫描

  1. package com.alg.Three;
  3. /** 最长公共前缀
  4.  * 纵向挨个比对字符是否相同
  5.  * @author fuyao
  6.  * @date 2022年06月20日 5:08 下午
  7.  */
  8. public class LongestCommonPrefix {
  10.     public String longestCommonPrefix(String[] strs) {
  11.         if (strs == null || strs.length == 0){
  12.             return "";
  13.         }
  15.         int length = strs[0].length();
  16.         int count = strs.length;
  17.         for (int i = 0; i < length; i++) {
  18.             for (int j = 1; j < count; j++) {
  19.                 if (strs[j].length() == i || strs[j].charAt(i) != strs[0].charAt(i)){
  20.                     return strs[0].substring(i);
  21.                 }
  23.             }
  24.         }
  25.         return strs[0];
  26.     }
  27. }

分治法

  1. public String longestCommonPrefix1(String[] strs) {
  2.         if (strs == null || strs.length == 0) {
  3.             return "";
  4.         } else {
  5.             return longestCommonPrefix(strs, 0, strs.length - 1);
  6.         }
  8.     }
  10.     private String longestCommonPrefix(String[] strs, int start, int end) {
  11.         if (start == end) {
  12.             return strs[start];
  13.         } else {
  14.             int mid = (end - start) / 2 + start;
  15.             String lcpLeft = longestCommonPrefix(strs, start, mid);
  16.             String lcpRight = longestCommonPrefix(strs, mid + 1, end);
  17.             return commonPrefix(lcpLeft, lcpRight);
  19.         }
  21.     }
  23.     private String commonPrefix(String lcpLeft, String lcpRight) {
  24.         int minlength = Math.min(lcpLeft.length(), lcpRight.length());
  25.         for (int i = 0; i < minlength; i++) {
  26.             if (lcpLeft.charAt(i) != lcpRight.charAt(i)) {
  27.                 return lcpLeft.substring(0, i);
  28.             }
  29.         }
  30.         return lcpLeft.substring(0, minlength);
  31.     }

二分法

  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.     }
  22.     public boolean isCommonPrefix(String[] strs, int length) {
  23.         String str0 = strs[0].substring(0, length);
  24.         int count = strs.length;
  25.         for (int i = 1; i < count; i++) {
  26.             String str = strs[i];
  27.             for (int j = 0; j < length; j++) {
  28.                 if (str0.charAt(j) != str.charAt(j)) {
  29.                     return false;
  30.                 }
  31.             }
  32.         }
  33.         return true;
  34.     }
  35. }