leetcode

Longest Common Prefix solution using TypeScript

Below is my TypeScript solution to the LeetCode "Longest Common Prefix" question.

Time Complexity: Because each character in each string will potentially be visited one time, the time complexity is O(s), where S represents the sum of all characters in all strings.

Space Complexity: This approach will use a constant amount of space, making the Space Complexity O(1).

/**
 * Find the longest common prefix string amongst an array of strings.
 *
 *   Time Complexity: O(s), s = sum of all characters in all strings
 *   Space Complexity: O(1)
 *
 *   Input: ["flower","flow","flight"]
 *   Output: "fl"
 *   Explanation: "fl" is the longest common prefix
 */
function longestCommonPrefix(strs: string[]): string {
    let i = 0;
    
    if (!strs.length) {
        return "";
    }
    
    while (true) {
        const char = strs[0][i] || "";
        const match = strs.every(str => str[i] === char);
        if (match) {
            i += 1;
        } else {
            break;
        }
    }
    return strs[0].slice(0, i);
};

more LeetCode posts