力扣最热一百题——最长公共前缀

题目链接：14. 最长公共前缀 - 力扣（LeetCode）

题目描述

示例

提示：

解法一：逐步缩减前缀

Java写法：

运行时间

C++写法：

运行时间

时间复杂度和空间复杂度

解法二：字典序排序

什么是字典序？

为什么通过字典序排序之后的首位字符串就可以找到最长公共前缀？

举例说明：

Java写法：

运行时间

C++写法：

运行时间

时间复杂度和空间复杂度

总结

题目链接：14. 最长公共前缀 - 力扣（LeetCode）

注：下述题目描述和示例均来自力扣

题目描述

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

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

示例

示例 1：

输入：strs = ["flower","flow","flight"]
输出："fl"

示例 2：

输入：strs = ["dog","racecar","car"]
输出：""
解释：输入不存在公共前缀。

提示：

1 <= strs.length <= 200
0 <= strs[i].length <= 200
strs[i] 仅由小写英文字母组成

解法一：逐步缩减前缀

这段代码的实现思路是基于一个假设开始的：它假设数组中的第一个字符串（strs[0]）是最长的公共前缀。然后，它遍历数组中的每个后续字符串（从strs[1]开始），并检查当前假设的公共前缀（prefix）是否仍然是这些字符串的前缀。

具体实现步骤如下：

处理空数组：首先，它检查传入的字符串数组strs是否为空或长度为0。如果是，那么没有公共前缀，直接返回空字符串。
初始化公共前缀：然后，它将数组中的第一个字符串（strs[0]）作为初始的公共前缀（prefix）。
遍历数组：接下来，它使用一个for循环遍历数组中的每个后续字符串（从索引1开始，即strs[1]到strs[strs.length - 1]）。
检查前缀：对于每个后续字符串，它使用indexOf方法检查当前假设的公共前缀（prefix）是否是该字符串的前缀（即indexOf(prefix)是否返回0）。
- 如果不是前缀（indexOf(prefix)不等于0），则进入一个while循环，逐步缩短prefix（通过移除prefix的最后一个字符），直到prefix成为该字符串的前缀或prefix变为空字符串。
- 如果在缩短prefix的过程中prefix变为空字符串，那么说明没有公共前缀，函数返回空字符串。
返回结果：如果遍历完所有字符串后都没有返回空字符串，那么说明prefix就是所有字符串的最长公共前缀，函数返回prefix。

当然了既然把这个方法放在第一位那么就是可以优化，这个实现虽然可以正确找到最长公共前缀，但它在有一些情况下可能不是最高效的。特别是，当prefix被缩短时，它可能会多次检查同一个较短的prefix是否是某个字符串的前缀，这是肯定是多余的了。但是由于力扣的测试用例说实话还是挺友善的，所以实现起来的速度还是挺快的。

Java写法：

class Solution {public String longestCommonPrefix(String[] strs) {// 处理空数组if (strs == null || strs.length == 0) {return "";  }// 假设第一个字符串是最长公共前缀String prefix = strs[0]; for (int i = 1; i < strs.length; i++) {// 如果当前字符串不以 prefix 开头while (strs[i].indexOf(prefix) != 0) {  // 缩短前缀prefix = prefix.substring(0, prefix.length() - 1);  // 如果前缀为空，返回空字符串if (prefix.isEmpty()) {return "";  }}}// 返回找到的最长公共前缀return prefix;  }
}

运行时间

C++写法：

class Solution {
public:string longestCommonPrefix(vector<string>& strs) {// 处理空数组if (strs.empty()) {return "";  }// 假设第一个字符串是最长公共前缀string prefix = strs[0];// 从第二个字符串开始遍历for (int i = 1; i < strs.size(); i++) {// 如果当前字符串不以 prefix 开头while (strs[i].find(prefix) != 0) {  // 缩短前缀prefix = prefix.substr(0, prefix.size() - 1);// 如果前缀为空，返回空字符串if (prefix.empty()) {return "";  }}}// 返回找到的最长公共前缀return prefix;}
};

运行时间

时间复杂度和空间复杂度

解法二：字典序排序

什么是字典序？

字典序（Lexicographical Order）是一种字符串排序方式，这个方式类似于我们在字典中查找单词时候的顺序。字符串根据其字符的排列方式，按照字母表的顺序进行排序。

例如，对于字符串 ["apple", "banana", "grape", "orange"]，按照字典序排序的结果是：

apple
banana
grape
orange

在字典序中，首先比较字符串的首字母，如果首字母相同，就比较第二个字母，依此类推。对于长度不同的字符串，如果前面几位都相同的话，那么就让较短的字符串排在前面。例如：

"abc" 排在 "abcd" 前面。

为什么通过字典序排序之后的首位字符串就可以找到最长公共前缀？

通过字典序排序后，数组的第一个字符串和最后一个字符串之间的公共前缀，实际上也是所有字符串之间的最长公共前缀。这是因为：

字典序是按照字符的逐个比较进行的，因此字典序排序后的第一个字符串和最后一个字符串在整个数组中具有最小和最大的“字母顺序”。
最小和最大的字符串之间的差异最大，换句话说，它们在前面相同的部分已经是所有字符串中公共前缀的最长部分。它们的不同部分意味着，其他字符串不可能有更长的公共前缀。
公共前缀只会出现在最小和最大字符串的前缀部分，因为如果最小字符串和最大字符串的前缀部分相同，其他字符串在这部分也一定相同。

举例说明：

假设字符串数组是：["flower", "flow", "flight"]，那么排序后结果就是：

"flight"
"flow"
"flower"

比较排序后的第一个字符串 "flight" 和最后一个字符串 "flower"，它们的最长公共前缀是 "fl"。因此，我们只需要比较第一个和最后一个字符串，酱紫找到它们的公共前缀就可以确定整个数组的最长公共前缀，因为其他字符串在这部分的前缀也必然是相同的。

Java写法：

import java.util.Arrays;class Solution {public String longestCommonPrefix(String[] strs) {// 获取数组长度int len = strs.length;// 如果数组为空，返回空字符串if (len == 0) {return "";}// 对字符串数组进行字典序排序Arrays.sort(strs);// 定义结果字符串，使用StringBuilder便于拼接字符串StringBuilder res = new StringBuilder();// 比较排序后第一个和最后一个字符串的相似部分for (int i = 0; i < strs[0].length() && i < strs[len - 1].length(); i++) {// 如果当前字符相同，加入结果if (strs[0].charAt(i) == strs[len - 1].charAt(i)) {res.append(strs[0].charAt(i));} else {// 如果不相同，结束循环break;}}// 返回结果return res.toString();}
}

运行时间

C++写法：

class Solution {
public:string longestCommonPrefix(vector<string>& strs) {// 数组长度int len = strs.size();// 对这个字符串数组进行字典序排序sort(strs.begin(), strs.end());// 定义出resstring res = "";// 找这俩的相似点for(int i = 0; i < strs[0].size() && i < strs[len - 1].size(); i++){// 一样就加进去if(strs[0][i] == strs[len - 1][i]){// 拼接答案res += strs[0][i];}else{// 不一样就说明到头了直接返回break;}}return res;}
};