[LeetCode Road] Longest Common Prefix - Solution/C++

14. Longest Common Prefix

Question:

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:

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

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

Constraints:

0 <= strs.length <= 200

0 <= strs[i].length <= 200

strs[i] consists of only lower-case English letters.

Source code

Version 1

Idea:
First, declared a variable of string that stored strs[0]. Then, I compared it with each elements of vector. At 8 line, min(res.length(), strs[i].length()) means finding a smallest length for matching between strings.

At 10 line, if a statement is true, I stored a current lenght of string and prepared to compare next element; if a statement is false, it means these strings aren't the same, so the length must be subtract 1 and compare each others again. At 17 line, if length is 0, there is no reason to execute althought maybe there are many elements that have not been compared.

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        if (strs.size() == 0) return "";
        string res = strs[0];
        int length = 0;
        for(int i = 1; i < strs.size(); i++){
            length = min(res.length(), strs[i].length());
            while(length > 0){
                if(res.substr(0, length) == strs[i].substr(0, length)){
                    res = strs[i].substr(0, length);
                    break;
                }else{
                    length --;
                }
            }
            if (length == 0) return "";
        }
        return res;
    }
};

Version 2

Idea:
A method is refered from online. Aims to compare every characters, if each characters is the same at the same position, store it!

The first loop is the length of strs[0] (1th string), the second loop is number of elements of vector. At 8 line, take each characters s[i] from every strings to match a character of strs[0][i], meanwhile, check the length of string whether it exceeds i index(position) or not. If a condtion is true, store this character strs[0][i]. On the contrary, return a record.

Time complexity: O(mk) // k: the length of common prefix, m: the number of strs
Space complexity: O(k)

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        if (strs.empty()) return "";
        string res;
        for (int i = 0; i < strs[0].length(); i++){
            for (const string &s : strs)
                if (s.length() <= i || s[i] != strs[0][i]) return res;
            res += strs[0][i];
        }
        return res;
    }
};