题目描述：
Description |
||
给你K个字符串，请求出它们的最长公共前缀。 输入 第一行是一个整数N，表示测试样例的个数。 每个测试样例的第一行是一个整数K（2 <= k <= 20），表示有多少个字符串；以后每行是一个字符串，每个字符串的长度不超过200个字符。 输出 每行输出一个样例的结果。先输出“Case #: ”，其中’#’为样例的序号（从1开始），冒号为英文冒号，后接一个空格；然后是对应样例的结果。如果没有公共前缀，则无需输出前缀，但Case信息仍需要输出。 |
||
Sample Input |
||
2 3 ACD ACDEF ACDFE 2 ABC BCD |
||
Sample Output |
||
Case 1: ACD Case 2: |
||
Source |
||
| ericxie |
思路：
方法一是横向扫描，依次遍历每个字符串，更新最长公共前缀。另一种方法是纵向扫描。纵向扫描时，从前往后遍历所有字符串的每一列，比较相同列上的字符是否相同，如果相同则继续对下一列进行比较，如果不相同则当前列不再属于公共前缀，当前列之前的部分为最长公共前缀。（参考力扣最长公共前缀力扣详解，详细解释请看代码注释）
//使用竖向扫描的方法解决
#include<stdio.h>
#include<string.h>
int pulicPre(int numCh,char ch[][200]);
int main(){
int k;
scanf("%d",&k);
int count = 1;
while(k--){
int n;
scanf("%d",&n);
char ch[n][200];//定义一个二维数组存放字符串
for(int i = 0;i < n;i++){
scanf("%s",ch[i]);
}
int right = pulicPre(n,ch);
printf("Case %d: ",count);
for(int i = 0;i < right;i++){
printf("%c",ch[0][i]);
}
printf("\n");
count++;
}
return 0;
}
int pulicPre(int numCh,char ch[][200]){
int len0 = strlen(ch[0]);//以第一个字符串为基准进行竖向扫描
for(int i = 0;i < len0;i++){//遍历第一个字符串的每一个字符,i代表从左到右第几个字符
char curCh = ch[0][i];//当前第一个字符串的第i个字符
for(int j=1;j<numCh;j++){//从第二个字符串开始向下遍历，j代表第几个字符串
int curLen = strlen(ch[j]);//当前被遍历字符串的长度
if(i == curLen || curCh != ch[j][i]){//i从0开始增长，
//一定会碰到最短字符串;当i == curLen时,说明遍历完最短字符串了
//curCh != ch[j][i] 没遍历到末尾，但是不相等
return i;
}
}
}
return len0;//没有提前跳出，说明第一个字符串就是最长公共子串
}- 为什么i从0开始增长一定会碰到最短字符串？
如果第一个字符串是最短字符串那么 minLen = Len0 ,如果第一个字符串不是最短字符串那么一定有 minLen < Len0, 综上，一定有minLen <= Len0;
- 注意:不要混淆i,j代表的含义—— i 代表第几列， j 代表第几个字符串
本文含有隐藏内容，请 开通VIP 后查看