My 4ms C++ solution which is straight forward to understand


  • 1
    R
    class Solution {
    public:
        string longestCommonPrefix(vector<string>& strs) {
            if (strs.size() == 0) return string();
            int i = 0;
            for (; i < strs[0].length(); ++i) {
                for (int j = 1; j < strs.size(); ++j) {
                    if (strs[j][i] != strs[0][i])
                        return strs[0].substr(0, i);
                }
            }
            return strs[0].substr(0, i);
        }
    };

  • 0
    E

    This algorithm seems to be suspicious.
    It returns as soon as the first character not matching.
    This is not necessarily the longest common prefix, e.g., "str", "sta", "s", it returns "st".
    However the correct answer should be "s".

    Also it is possible to access invalid memory locations, e.g., "str", "s", the algorithm might go and check two positions after "s".


  • 0
    R

    I don't think your case is valid. Do you try test cases you mentioned? For the "invaild memory access", a string always has trailing 0, then this is the case for a whole string as lcp


  • 0
    E

    Hi raof01, you are right about my first comment. It is returning the LCP. But I am not convinced by the trailing 0 trick, because it relies more or less on a compiler implementation detail.
    Not all string implementation follow this way.

    Although I did not implement the algorithm as the following, I prefer go through the vector to identify the shortest string, and start from there.
    We might even use binary search to speed up a little bit (Is the full length of the shortest string the LCP? Is half of it? etc. ).


  • 0
    R

    The trailing 0 is not a trick, this is what standard C++ does


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.