题目
注：本题来自LeetCode题库14.最长公共前缀。
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 “”。
示例1：
1
2
| 输入: ["flower","flow","flight"]
输出: "fl"
|
示例2：
1
2
3
| 输入: ["dog","racecar","car"]
输出: ""
解释: 输入不存在公共前缀。
|
解法1：字符串排序取首尾公共前缀
简单来说，把字符串按字母顺序排序后，首字符串和尾字符串的公共前缀，就是这一组字符串的公共前缀。这种解法用C语言并不是很好实现。因为Python中内置函数min()和max()，在这里我使用Python 3来解决。代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| # 语言：Python 3
# 执行用时：36ms
# 内存消耗：12.8MB
class Solution:
def longestCommonPrefix(self, strs: List[str]) -> str:
if not strs:
return ""
strMin = min(strs)
strMax = max(strs)
string = []
for i in range(0, len(strMin)):
if strMin[i] == strMax[i]:
string.append(strMin[i])
else:
break
return "".join(string)
|
解法2：取最短字符串逐个比对
上面的解法依赖于Python的内置函数min()和max()。我们换一种思路，取出其中最短的字符串，用它和其他的字符串一一比对，找出公共前缀。
特殊地，如果输入的字符串数组长度为0，则只需返回空字符串“”；如果输入的字符串数组长度为1，则只需返回这个字符串，即strs[0]。
代码如下：
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
31
32
33
34
35
| // 语言：C
// 执行用时：0ms
// 内存消耗：7.1MB
char * longestCommonPrefix(char ** strs, int strsSize){
int strLen = 0;
char *shortStr = NULL;
int shortLen = 0;
int i, j;
if (strs == NULL || strsSize == 0)
return "";
if (strs != NULL && strsSize == 1)
return strs[0];
shortStr = strs[0];
shortLen = strlen(strs[0]);
for (i = 0; i < strsSize; i++) {
strLen = strlen(strs[i]);
if (shortLen > strLen) {
shortLen = strLen;
shortStr = strs[i];
}
}
for (j = 0; j < shortLen; j++) {
for (i = 0; i < strsSize; i++) {
if (strs[i][j] != shortStr[j]) {
if (j == 0) {
return "";
} else {
shortStr[j] = '\0';
return shortStr;
}
}
}
}
return shortStr;
}
|
解法3：水平扫描法
为了便于理解，我截取了LeetCode官方题解中水平扫描法的图解：
代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| 语言：C
执行用时：4ms
内存消耗：7.1MB
char * longestCommonPrefix(char ** strs, int strsSize){
int i, j;
if (strsSize == 0)
return "";
if (strsSize == 1)
return strs[0];
for (i = 0; i < strlen(strs[0]); i++) {
for (j = 1; j < strsSize; j++)
if (strs[0][i] != strs[j][i]) {
strs[0][i] = '\0';
}
}
return strs[0];
}
|
解法4：使用Python的os.path模块
最后放一个“大招”吧。正所谓“人生苦短，我用Python”，就在Python的os.path模块中，有一个叫做commonprefix()的方法，可以说是为这道题而生。
我们来对os.path.commonprefix()做一下说明。它可以返回list(多个路径)中所有path共有的最长的路径。怎么样，是不是完美适配这道题呢？
还是放一下代码吧，虽然只有短短一行：
1
2
3
4
5
6
| # 语言：Python 3
# 执行用时：28ms
# 内存消耗：12.7MB
class Solution:
def longestCommonPrefix(self, strs: List[str]) -> str:
return os.path.commonprefix(strs)
|