Longest Common Prefix

Description

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(javascript)

/**
 * @param {string[]} strs
 * @return {string}
 */
var longestCommonPrefix = function(strs) {
    // If the string is empty return empty string
     if (strs.length === 0) return "";
    // The prefix is the start of the word
    let prefix = strs[0];
    // Iterate over the array
    for (let i = 1; i < strs.length; i++)
        // Returns -1 or 0. 0 if the char matches the prefix
        while (strs[i].indexOf(prefix) !== 0) {
            // slices the prefix from the start to the char
            prefix = prefix.substring(0, prefix.length - 1);
            if (prefix.length === 0) return "";
        }        
    return prefix;
};
// Time: O(n), where n is the sum of all the characters in all strins
// Space: O(1)
← Palindrome Number3Sum →