14. 最长公共前缀

🟢   🔖  字典树 字符串  🔗 力扣 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.

题目大意

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

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

解题思路

思路一：循环比较

1. 将字符串数组按照字符串长度，从小到大排序；
2. 初始化公共前缀为字符串数组中的第一个字符串；
3. 然后将数组中的字符串与公共前缀依次比较，每次比较出不同时就缩小公共前缀，直到公共前缀为空或者遍历完所有字符串数组。

复杂度分析

• 时间复杂度：O(m * n)，其中 m 是 strs 中最短的字符串的长度，n 是 strs 中字符串的个数；
  • 排序的时间复杂度是 O(n log n)；
  • 遍历寻找公共前缀的时间复杂度是 O(m * n)；
  • 遍历数组，需要循环 n - 1 次，内部的 while 循环中字符串会与公共前缀依次比较，每次比较出不同时就缩小公共前缀，最坏的情况需要比较 m 次；
    • 在大多数情况下，当字符串数量 (n) 和最短字符串的长度 (m) 很大时，O(m * n) 将占主导地位，因此时间复杂度是 O(m * n)。
• 空间复杂度：O(1)，使用的额外空间复杂度为常数。

---

思路二：二维数组

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

复杂度分析

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

代码

循环比较

/**
 * @param {string[]} strs
 * @return {string}
 */
var longestCommonPrefix = function (strs) {
	strs.sort((a, b) => a.length - b.length);
	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];
};