14. Longest Common Prefix

🟢   🔖  字典树 字符串  🔗 LeetCode

题目

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 lowercase English letters.

题目大意

编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀，返回空字符串 ""。

解题思路

思路一：循环比较

初始化公共前缀为字符串数组中的第一个字符串，然后将数组中的字符串与公共前缀一依次比较，每次比较出不同时就缩小公共前缀，直到公共前缀为空或者遍历完所有字符串数组。

• 时间复杂度：O(len(strs[0])) 或 O(len(strs))
• 空间复杂度：O(len(strs[0]))

思路二：二维数组

把字符串列表看成一个二维数组，然后用一个嵌套 for 循环计算这个二维数组前面有多少列的元素完全相同即可。

• 时间复杂度：O(mn)，其中 m 是字符串数组中的字符串的平均长度，n 是字符串的数量。最坏情况下，字符串数组中的每个字符串的每个字符都会被比较一次。
• 空间复杂度：O(1)，使用的额外空间复杂度为常数。

代码

循环比较

/**
 * @param {string[]} strs
 * @return {string}
 */
var longestCommonPrefix = function (strs) {
	let pref = strs[0],
		prefLen = pref.length;
	for (let i = 1; i < strs.length; i++) {
		let s = strs[i];
		while (pref !== s.substring(0, prefLen)) {
			prefLen--;
			if (prefLen == 0) return '';
			pref = pref.substring(0, prefLen);
		}
	}
	return pref;
};

二维数组

/**
 * @param {string[]} strs
 * @return {string}
 */
var longestCommonPrefix = function (strs) {
	for (let i = 0; i < strs[0].length; i++) {
		for (let j = 0; j < strs.length; j++) {
			if (i >= strs[j].length || strs[0][i] != strs[j][i]) {
				return strs[0].slice(0, i);
			}
		}
	}
	return strs[0];
};