LeetCode 腾讯精选练习50 题——14. 最长公共前缀

题目

解答

1. 方法一

第一个字符串和第二个匹配得出一个公共前缀后，再用这个前缀与下一个字符串匹配，重复下去到最后一个，代码如下：

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        if(strs.size() == 0)
            return "";
        string prefix  = strs[0];
        for(int i = 1; i < strs.size(); i++) {
            int j = 0;
            for(; j < min(prefix.length(), strs[i].length()); j++)
                if(strs[i][j] != prefix[j])
                    break;
            prefix = prefix.substr(0,j);
        }
        return prefix;
    }
};

2. 方法二（分治法）

答案思路：首先找到所有字符串中最短的一个，然后再对这个字符串进行二分：先使用左边部分去遍历全部字符串，如果这个部分是公共前缀，则去使用右边部分去遍历全部字符串；如果不是公共前缀，则继续将左边部分的字符串划分为两等份，重复上面的操作。

PS：这个方法不仅实现起来麻烦，时间复杂度还比方法一大，我当时实现答案这个思路是因为我懒得去分析，直接默认答案越后面的方法的用时越少了......

代码如下：

【注意】注意判断某字符串是否为最长公共前缀的函数isPrefix的输入参数中，min是字符串数组中最短的字符串所在下标，length则是（截取字符串部分的长度 - 1）即每次检查的是strs[min][0] ~ strs[min][length]是否为最长公共前缀。之所以在longestCommonPrefix中的返回是(low+high)/2 + 1而不是mid，是因为能跳出while循环到达返回这里有两种情况：

1）low = mid+1执行完后，low > high，这时候，low比high大1，且0-mid+1才是最长公共前缀

2）high = mid-1执行完后，low>high，这时候，low比high大1，且0-mid是最长公共前缀，这个时候，high所在位置就是mid，且 (low+high) / 2等于mid

其中值得提醒一点的是，要在while的判断语句中出现low>high这种情况，在前一次的循环必定会有low == high，那么low比high大的时候，也只是大1而已。因为low(high)的每次更新都是取二者的中值加一(减一)，这就导致了在low不等于high的情况，在一次更新中就能达到low最多只能增加到high，或者high最多可以减少到low。

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        if(strs.size() == 0)
            return "";
        int min_val = INT_MAX, min = 0;
        for(int i = 0; i < strs.size(); i++)
            if(strs[i].length() < min_val) {
                min_val = strs[i].length();
                min = i;
            }
        int low = 0, high = strs[min].length()-1, mid = 0;
        while(high >= low) {
            mid = (low+high) / 2;
            if(isPrefix(strs, min, mid))
                low = mid + 1;
            else
                high = mid - 1;
        }
        if(high < 0)
            return "";
        return strs[min].substr(0,(low+high)/2 + 1);
    }
private:
    bool isPrefix(vector<string>& strs, int min, int length) {
        for(int i = 0; i < strs.size(); i++) {
            for(int j = 0; j <= length; j++) {
                if(strs[i][j] != strs[min][j])
                    return false;
            }
        }
        return true;
    }
};