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).