本文共 2744 字，大约阅读时间需要 9 分钟。

最长公共前缀（Longest Common Prefix）

问题描述

最长公共前缀（Longest Common Prefix，简称LCP）问题要求找出一组字符串中共同拥有的最长前缀部分。例如，给定字符串数组 ["abc", "abd", "abcef"]，它们的最长公共前缀是 "ab"。

方法一：分治法

分治法通过将问题分解为更小的问题来解决。具体步骤如下：

最大效率发生在递归深度增加时，分治法的时间复杂度为 O(mn)，其中 m 是字符串的平均长度，n 是字符串数量。这种方法在处理较小规模问题时表现优异。

方法二：二分查找法

二分查找法利用最短字符串的最大长度范围内进行高效搜索。具体步骤如下：

这方法充分利用了二分搜索的优势，时间复杂度为 O(mn log m)，适合大规模问题的处理。

代码实现

以下是基于以上两种方法的代码实现：

分治法实现

class Solution {    public:        string longestCommonPrefix(vector
   
     &strs) {            if (strs.size() === 0) return "";            return longestCommonPrefix(strs, 0, strs.size() - 1);        }        string longestCommonPrefix(const vector
    
      &strs, int start, int end) {            if (start === end) return strs[start];            int mid = (start + end) / 2;            string left = longestCommonPrefix(strs, start, mid);            string right = longestCommonPrefix(strs, mid + 1, end);            return commonPrefix(left, right);        }        string commonPrefix(const string &a, const string &b) {            int minLength = min(a.size(), b.size());            for (int i = 0; i < minLength; ++i) {                if (a[i] != b[i]) return a.substr(0, i);            }            return a.substr(0, minLength);        }}
    
   

二分查找实现

#include 
   
    #include 
    
     #include 
     
      using namespace std;class Solution {    public:        string longestCommonPrefix(vector
      
        &strs) {            if (strs.empty()) return "";            int minLength = min_element(strs.begin(), strs.end(), [](const string &a, const string &b) {                return a.size() < b.size();            }).second;            int low = 0, high = minLength;            while (low < high) {                int mid = (high - low + 1) / 2;                if (isCommonPrefix(strs, mid)) {                    low = mid;                } else {                    high = mid - 1;                }            }            return strs[0].substr(0, low);        }        bool isCommonPrefix(const vector
       
         &strs, int length) {            string ref = strs[0].substr(0, length);            for (const string &s : strs) {                for (int i = 0; i < length; ++i) {                    if (ref[i] != s[i]) return false;                }                return true;            }            return true;        }}
       
      
     
    
   

时间复杂度分析

• 分治法： O(mn)，因为每次分解问题时，字符串数量减半，比较次数也减少。
• 二分查找法： O(mn log m)，二分的次数以及每次检查的字符串数量决定了复杂度。

父题解答扩展

这个问题属于比较典型的字符串处理问题，解法有分治和二分两种。选择哪种方法取决于具体需求，比如处理规模和效率需求。希望以上解释能帮助你更好地理解和实现这个问题。

转载地址：http://ncwqz.baihongyu.com/