Simple O(n*min(m)) solution with comments


  • 0
    O
    function longestCommonPrefix(strs) {
        if (!strs || !strs.length) { return ''; }
        if (strs.length === 1)     { return strs[0]; }
        
        // 1. Find the string with the smallest length. No need
        // to check characters after that.
        
        let minStrLength = strs[0].length;
        
        for (let i = 1; i < strs.length; ++i) {
            if (strs[i].length < minStrLength) {
                minStrLength = strs[i].length;
            }
        }
        
        // 2. Just look at all strings one character by one
        // character. As soon as there is a string with a
        // character that doesn't match the other strings,
        // we can return a substring.
        
        for (let i = 0; i < minStrLength; ++i) {
            const char = strs[0][i];
            
            for (let j = 1; j < strs.length; ++j) {
                if (strs[j][i] !== char) {
                    return strs[0].substring(0, i);
                }
            }
        }
        
        // 3. If we exited the loop, it means that all strings
        // have a common prefix with length "minStrLength".
        
        return strs[0].substring(0, minStrLength);
    };
    

Log in to reply
 

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