LeetCode最长公共前缀——C

ゞ浴缸里的玫瑰 2021-10-29 11:44 297阅读 0赞

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/longest-common-prefix

## 题目描述 ##

编写一个函数来查找字符串数组中的最长公共前缀。  
如果不存在公共前缀，返回空字符串 “”。

示例 1:  
输入: \[“flower”,“flow”,“flight”\]  
输出: “fl”

示例 2:  
输入: \[“dog”,“racecar”,“car”\]  
输出: “”  
解释: 输入不存在公共前缀。

说明:  
所有输入只包含小写字母 a-z 。

## 题解 ##

这道题我想到的就是依次比较，就是水平查找法，当第 i 个字符不相等时就退出。

## 代码 ##

char* longestCommonPrefix(char** strs, int strsSize) {
    	if (strsSize == 0) {					// 没有就直接返回 "" 
    		char* ret = (char*)malloc(1);
    		ret[0] = '\0';
    		return ret;
    	}
    	int count = 0;							// 水平查找第几个
    	int flag = true;						// 表示是否退出 
    	char c;									// 第一个字符串的标准 
    	char* str = (char*)calloc(128 , sizeof(char));						//分配空间128（至少），并初始化 
    	while (flag) {
    		c = strs[0][count];
    		for (int j = 0; j < strsSize; j++) {
    			if ((strs[j][count]=='\0') || (strs[j][count] != c)) {		//退出条件 
    				flag = false;
    				break; 
    			}
    		}
    		str[count] = c;						// 一样的字符保存 
    		count++;
    	}
    	str[count-1] = '\0';					// 去除最后一个 
    	return str;
    }

## 结果 ##

#include <stdio.h>
    #include <string.h>
    #include <stdlib.h>
    
    int main()
    {
    	const char* s[] = { "flower","flow","flight" };
    	char** strs = (char**)s;
    	char* buff = longestCommonPrefix(strs, 3);
    	puts(buff);
    	return 0;
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEwOTAxMg_size_16_color_FFFFFF_t_70]![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEwOTAxMg_size_16_color_FFFFFF_t_70 1]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEwOTAxMg_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20190815203521873.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEwOTAxMg==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEwOTAxMg_size_16_color_FFFFFF_t_70 1]: /images/20211029/fab91603e64347f8b38d48b99bc72fb4.png