编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀,返回空字符串 ""。
示例 1:
输入:strs = ["flower","flow","flight"]
输出:"fl"
示例 2:
输入:strs = ["dog","racecar","car"]
输出:""
解释:输入不存在公共前缀。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/longest-common-prefix
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
解题思路:
这道题从我们新手小白的角度去想其实是有三种的解题思路。
第一种解题思路是:在拿该字符串数组的首元素去和剩下的元素进行一个一个字符去比较,当出现某一行某一列有一个字符(注意是字符)和首元素中的同一列的字符不相同时,直接在首元素的这一列上赋值'\0'。
代码1:
char * longestCommonPrefix(char ** strs, int strsSize){
int i,j;
int len = strlen(strs[0]);//通过首元素的字符串的长度求出列数
int flag = 0;
for(i = 0;i < len;i++)//列数
{
for(j = 1;j < strsSize;j++)//行数
{
if(strs[0][i] != strs[j][i])//判断首元素的每一列的字符是否和后面行数同列字符相同
{
strs[0][i] = '\0';
flag = 1;
break;
}
}
if(flag == 1)
{
break;
}
}
if(strlen(strs[0]) == 0)
{
return "";
}
else
{
return strs[0];
}
}
第二种解题思路跟第一种解题思路差不多,第二种解题思路:先是找到字符串数组中长度最短的那个字符串,为什么要找长度最短的字符串呢?因为要找出公共的字符串肯定是以最短的字符串长度作为界限,因为一旦超过这个长度其他的字符串在怎么比较也是无用功的。然后找出公共字符串 的步骤和第一种方法差不多,最后在开辟一个动态内存去存公共字段
char * longestCommonPrefix(char ** strs, int strsSize){
int i,j,len = 0;
len = strlen(strs[0]);//假设最短长度的字符串是strs[0]
int flag = 0;
char temp;
int num = 0;
for(i = 1;i < strsSize;i++)
{
if(strlen(strs[i]) < len)//与len进行比较,发现有比它还小的就进行替换
{
len = strlen(strs[i]);
}
}
for(i = 0;i < len;i++)
{
temp = strs[0][i];
for(j = 1;j < strsSize;j++)
{
if(temp != strs[j][i])//找寻公共字段
{
flag = -1;
break;
}
}
if(flag == -1)
{
break;
}
num++;
}
char *p = (char *)malloc(sizeof(char) * (num + 1));//开辟动态内存
for(i = 0;i < num;i++)
{
p[i] = strs[0][i];
}
p[i] = '\0';
return p;
}
(其实上面的flag可以不用定义的,因为定义了个变量导致用时和内存消耗增加了,其实那个flag可以随便用i或者j去顶替就行,我这里写个flag是为了能更好的理解)
最后欢迎评论留言,欢迎各位大佬指教!!!谢谢!!!
版权声明:本文为m0_59083833原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接和本声明。