14-最长公共前缀

LeetCode 14. Longest Common Prefix

Write a function to find the longest common prefix string amongst an array of strings.

If there is no common prefix, return an empty string “”.

Example 1:

Input: strs = ["flower","flow","flight"]
Output: "fl"

Example 2:

Input: strs = ["dog","racecar","car"]
Output: ""
Explanation: There is no common prefix among the input strings.

method

假设第一个字符串为公共前缀，将其与其他字符串逐个比较，逐渐缩短前缀

string longestCommonPrefix(vector<string>& strs) {
    string res = strs[0];
    for (int i = 1; i < strs.size(); i++) {
        int p = 0;  // 用指针来比较，相同就往后移
        int len = min(res.size(), strs[i].size());  // 不能超过较短的长度
        while (p < len && res[p] == strs[i][p]) p++;
        res = res.substr(0, p); // 前缀缩短
        if (res.size() == 0) return "";
    }
    return res;
}