14. Longest Common Prefix
Tags
- String
Write a function to find the longest common prefix string amongst an array of strings.
题意：
写一个查找字符串数组中最长公共前缀字符串的函数
分析：
又是字符串问题，又是公共。那方法就很简单咯，就是将数组中的每个字符串两两对比每个字符串的每个字符，返回公共的子字符串即可。
思路：
- 以数组中的某个字符串为基准；
- 循环比较两个字符串中的每个字符，找到最长公共前缀字符串，然后把位置记录下来，将基准字符串按此截掉，留下公共部分；
- 直到数组中的每个字符串都与基准字符串比较完毕为止，返回公共子串
JS实现：
复杂度
时间复杂度O(n2)
方法 #1 以第一个字串为基准字符串
/**
* @param {string[]} strs
* @return {string}
*/
var longestCommonPrefix = function(strs) {
if(strs ===null || strs.length ===0) {
return "";
}
let prefix = strs[0];
for(let i = 0; i < strs.length; i++){
let j = 0;
while(j < strs[i].length && j < prefix.length && strs[i].charAt(j)===prefix.charAt(j)){
j++;
}
if(j===0) {
return "";
}
prefix = prefix.substring(0,j);
}
return prefix;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
方法 #2 找数组中最短字符串为基准循环
/**
* @param {string[]} strs
* @return {string}
*/
var longestCommonPrefix = function(strs) {
if(strs ===null || strs.length ===0) {
return "";
}
if(strs.length === 1) {
return strs[0];
}
let minlen = strs.length + 1;
for(let str of strs) {
if(minlen > str.length) {
minlen = str.length;
}
}
for(let i = 0; i < minlen;i++){
for(let j = 0; j < strs.length - 1;j++){
let str1 = strs[j];
let str2 = strs[j+1];
if(str1.charAt(i) !== str2.charAt(i)) {
return str1.substring(0,i);
}
}
}
return strs[0].substring(0,minlen);
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30