C++ O(m*n) Time O(1) Space


  • 0
    M

    We add 1 next character each cycle and check if that character is present in all strings. In worst case (all strings are equal) we do m character cycles and check it in n strings.

    class Solution {
    public:
        string longestCommonPrefix(vector<string>& strs) {
            if (strs.empty()) return "";
            for (int len = 0; ; ++len) {
                char c = strs.front()[len];
                for (auto& s: strs)
                    if (s.size() <= len || s[len] != c)
                        return strs.front().substr(0, len);
            }
        }
    };
    

Log in to reply
 

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