算法 14. 最长公共前缀

LeetCode https://leetcode.cn/problems/longest-common-prefix/

题目描述

编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 “”。

思路

依次遍历, 更新公共前缀即可

代码

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

    std::string longestCommonPrefix(const std::string& str1, const std::string& str2, size_t prefix_size) {
        int length = min(str1.size(), str2.size());
        int index = 0;
        while (index < length && str1[index] == str2[index] && index <= prefix_size) {
            ++index;
        }
        return str1.substr(0, index);
    }
};