LeetCode 14. Longest Common Prefix [Easy] [C++] 解題筆記

這題給我們一些字串，要我們找出這些字串的最長 prefix string。

EX:

        Input: ["flower","flow","flight"]

    Output: "fl"

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

想法:

    這題基本上沒啥特別作法，就是暴力搜索而已，以第一個字串當做基準，逐個搜索其他字串的當前字元是否與第一個

字串相等，若有其中一個長度不夠或是不相等就可以直接返回了。

Complexity: O(c*n) time, O(1) space. , 

where c is len of common prefix, n is number of string in strs 

完整程式碼:

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        if (strs.empty()) { return ""; }
        string prefix = "";
        int cur_idx = 0;
        while (1) {
            if (strs[0].size() <= cur_idx) { 
                return prefix;
            }
            auto cur = strs[0][cur_idx];
            for (int i = 1; i < strs.size(); i++) {
                if (strs[i].size() <= cur_idx) { 
                    return prefix;
                }
                if (strs[i][cur_idx] != cur) {
                    return prefix;
                }
            }
            prefix.push_back(cur);
            cur_idx++;
        }
         
        return prefix;
    }
};