[LeetCode] Longest Common Prefix

https://leetcode.com/problems/longest-common-prefix/?tab=Description

没什么可说的，比较简单，挨个遍历即可。

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        if (strs.empty()) return "";
        
        string ret = strs[0];
        for (int i = 1; i < strs.size(); ++i) {
            // get the LCP of ret and strs[i]
            int j = 0;
            while (j < ret.size() && j < strs[i].size() && ret[j] == strs[i][j]) ++j;
            ret = ret.substr(0, j);
        }
        
        return ret;
    }
};

优化一下：

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        if (strs.empty()) return "";
        
        string& ret = strs[0];
        int j = ret.size();  // the upper bound of LCP
        
        for (int i = 1; i < strs.size(); ++i) {
            if (strs[i].size() < j) j = strs[i].size();
        }
        
        for (int i = 1; i < strs.size(); ++i) {
            // get the LCP of ret and strs[i]
            int k = 0;
            while (k < j && ret[k] == strs[i][k]) ++k;
            j = k;
        }
        
        return ret.substr(0, j);
    }
};