题目描述
编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀，返回空字符串 ""。
示例 1:
输入: ["flower","flow","flight"]
输出: "fl"示例 2:
输入: ["dog","racecar","car"]<
输出: ""
解释: 输入不存在公共前缀。
说明: 所有输入只包含小写字母 a-z 。
解析
垂直扫描法
水平扫描法
- 取出第一个字符串暂时作为最长公共前缀（prefixStr）；
- 依次遍历字符串数组中的其他字符串，分别与prefixStr比较；
- 若当前字符不包含prefixStr，则对prefixStr进行裁取（长度减一），再次与当前字符进行比较；
- 若当前字符包含prefixStr，则取出字符串数组的下一个字符串与prefixStr进行比较；
代码实现
- 时间复杂度：O(S)，S是所有字符串中字符数量的总和，最坏情况时n个字符串全部相同，则indexOf要比较S次字符比较
- 空间复杂度：O(1)
class Solution {
public String longestCommonPrefix(String[] strs) {
if(strs.length == 0) return "";
String prefixStr = strs[0];
for(int i = 1; i < strs.length; i++){
while(strs[i].indexOf(prefixStr) != 0){
prefixStr = prefixStr.substring(0,prefixStr.length() - 1);
if(prefixStr.isEmpty()) return "";
}
}
return prefixStr;
}
}
水平扫描法
- 取出字符串数组中的第一个字符串，遍历该字符串中的字符，依次与数组中的其他字符串的同列字符比较；
- 若出现不同的字符，则对第一个字符串进行相应位置截取，便得最长公共前缀；
- 若某字符串长度等于当前所比较字符位置（i = strs[j].length()），则也进行第2步的截取操作；
代码实现
- 时间复杂度: O(S)，S 是所有字符串中字符数量的总和
- 空间复杂度: O(1)
class Solution {
public String longestCommonPrefix(String[] strs) {
if(strs == null || strs.length == 0) return "";
for(int i = 0; i < strs[0].length(); i++){
char a = strs[0].charAt(i);
for(int j = 1; j < strs.length; j++){
if( i == strs[j].length() || a != strs[j].charAt(i)){ // 先执行||, 然后执行后面, 且i == strs[j].length()表示存在字符串已经遍历完
return strs[0].substring(0,i);
}
}
}
return strs[0];
}
}
