题解 | #牛族寻找祖先# 字符串

知识点

字符串

思路

把备选答案设置为第一个名字，遍历整个字符串数组，取出备选答案和当前字符串的最长公共前缀作为下一轮的答案。

时间复杂度

n为字符串数组的长度，m为每个字符串的长度。

AC Code（C++）

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param names string字符串vector 
     * @return string字符串
     */
    string findAncestor(vector<string>& names) {
        string res = names[0];
        for (int i = 1; i < names.size(); i ++) {
            get(res, names[i]);
        }
        return res;
    }
    void get(string& res, string& s) {
        int sz = 0;
        while (sz < res.size() and sz < s.size() and res[sz] == s[sz]) {
            sz ++;
        }
        res.resize(sz);
    }
};