categories: [Blog,Algorithm]

14. 最长公共前缀

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

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

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

提示：

  • 0 <= strs.length <= 200
  • 0 <= strs[i].length <= 200
  • strs[i] 仅由小写英文字母组成.
  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.     }
  16.     public String longestCommonPrefix(String str1, String str2) {
  17.         int length = Math.min(str1.length(), str2.length());
  18.         int index = 0;
  19.         while (index < length && str1.charAt(index) == str2.charAt(index)) {
  20.             index++;
  21.         }
  22.         return str1.substring(0, index);
  23.     }
  25. 作者：LeetCode-Solution
  26. 链接：https://leetcode-cn.com/problems/longest-common-prefix/solution/zui-chang-gong-gong-qian-zhui-by-leetcode-solution/
  1. class Solution {
  2.     public String longestCommonPrefix(String[] strs) {
  3.         if (strs == null || strs.length == 0) {
  4.             return "";
  5.         }
  6.         int length = strs[0].length();
  7.         int count = strs.length;
  8.         for (int i = 0; i < length; i++) {
  9.             char c = strs[0].charAt(i);
  10.             for (int j = 1; j < count; j++) {
  11.                 if (i == strs[j].length() || strs[j].charAt(i) != c) {
  12.                     return strs[0].substring(0, i);
  13.                 }
  14.             }
  15.         }
  16.         return strs[0];
  17.     }
  18. }
  20. 作者：LeetCode-Solution
  21. 链接：https://leetcode-cn.com/problems/longest-common-prefix/solution/zui-chang-gong-gong-qian-zhui-by-leetcode-solution/

解析

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