14. 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: ["flower","flow","flight"] Output: "fl" 

Example 2:

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

Note:

All given inputs are in lowercase letters a-z.

Solution

/** * @param {string[]} strs * @return {string} */ var longestCommonPrefix = function(strs) { if (strs.length === 0) return ''; var len1 = strs.length; var len2 = strs[0].length; var tmp = ''; var res = ''; outer: for (var i = 0; i < len2; i++) { tmp = strs[0][i]; inner: for (var j = 1; j < len1; j++) { if (strs[j][i] !== tmp) break outer; } res += tmp; } return res; }; 

Explain:

nope.

Complexity:

• Time complexity : O(n^2).
• Space complexity : O(1).