题目
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 “”。
示例 1:
1
2
| 输入: ["flower","flow","flight"]
输出: "fl"
|
示例 2:
1
2
3
4
| 输入: ["dog","racecar","car"]
输出: ""
解释: 输入不存在公共前缀。
说明:
|
所有输入只包含小写字母 a-z 。
解法
解法一：水平扫描法
首先，我们将描述一种查询一组字符串的最长公共前缀 LCP(S1...Sn)，我们得到结论是：
LCP(S1...Sn)=LCP(LCP(LCP(S1,S2),S3),...Sn)
从公式可以看出，两两比较的字符串的公共字符串就是我们的运算过程。
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
36
37
38
39
40
41
42
43
44
| #include <stdio.h>
#include <string.h>
#include <stdlib.h>
char *longestCommonPrefix(char **strs, int strSize)
{
int i, j;
if (strSize == 0)
{
return "";
}
char *str = (char *)malloc(sizeof(char) * 1000);
strcpy(str, strs[0]);
for (i = 1; i < strSize; i++)
{
j = 0;
while (str[j] && strs[i][j] && str[j] == strs[i][j])
{
j++;
}
str[j] = '\0';
}
return str;
}
int main()
{
char *strs[] = {"lees", "leetcode", "leet", "leets"};
int size = sizeof(strs) / sizeof(char *);
char *lcp;
lcp = longestCommonPrefix(strs, size);
printf("%s\n", lcp);
return 0;
}
|
具体请查看我的 github 仓库项目
leetcode-practice