Longest Common Prefix

Problem

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 1:

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

Example 2:

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

Constraints:

1 <= strs.length <= 200
0 <= strs[i].length <= 200
strs[i] consists of only lower-case English letters.

Solution

/**
 * @param {string[]} strs
 * @return {string}
 */
var longestCommonPrefix = function(strs) {
    if (!strs.length) {
        return "";
    }
    let dp = Array(strs.length).fill(null);
    dp[0] = strs[0];

    for (let i = 1; i < strs.length; ++i) {
        let count = 0;
        let n = Math.min(dp[i - 1].length, strs[i].length);
        for (let j = 0; j < n; ++j) {
            if (dp[i - 1][j] !== strs[i][j]) {
                break;
            } else {
                count++;
            }
        }
        dp[i] = strs[i].substring(0, count);
    }
    return dp[strs.length - 1];
};

We will implement a DP solution. Let dp[i] be the longest common prefix of array strs[0:i + 1].

For the base case, if i = 0, dp[0] = strs[0] since that's the only string in strs[0:1].
For the recursive case, the longest common prefix including the current string strs[i] is the longest common prefix of dp[i - 1] and strs[i] (ie. the longest common prefix amongst all the strings in strs[0:i] and the current string).

Problem​

Solution​

Problem

Solution