LeetCode 014 Longest Common Prefix 题解

题意

给一堆字符串,求这一堆字符串的最长公共前缀

分析

这个题目比较简单,读了几遍题才确定确实是如此简单。最长公共前缀,意味着起点就固定在第一个字符,所以就依次检测所有字符串的第2个、第3个字符……直到有某个字符串的下一个字符与别人不同为止。

C代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
char* longestCommonPrefix(char** strs, int strsSize) {
char c;
int n = 0;
if(strsSize == 0) return "";
for(int i = 0; ; i++) // H
{
int j;
c = strs[0][i];
if(c == 0) break;
for(j = 0; j < strsSize; j++) // V
{
if(c != strs[j][i]) break;
}
if(j != strsSize) break;
else n++;
}
strs[0][n] = 0;
return strs[0];
}

需要特别判断的是输入字符串为空,则返回空字符串""。外层循环是横向指针,指到每个字符串的第几个字符。内层循环是纵向指针,在不同字符串的同一个位置间跳转。内层循环之前将下一个公共字符初始化为第一个字符串的下一次字符,注意判断字符串的结尾即可。


版权声明

The Bloom of Youth by KUANG Qi is licensed under a Creative Commons BY-NC-ND 4.0 International License.
况琪创作并维护的锦瑟华年博客采用创作共用保留署名-非商业-禁止演绎4.0国际许可证

本文首发于The Bloom of Youth | 锦瑟华年博客( http://kuangqi.me ),版权所有,侵权必究。

本文永久链接:http://kuangqi.me/programming/leetcode-longest-common-prefix/