LeetCode-Algorithms-14. Longest Common Prefix（最长公共前缀）

1. 题目描述

编写一个函数来查找字符串数组中的最长公共前缀。 如果不存在公共前缀，返回空字符串 ""。 示例 1: 输入: ["flower","flow","flight"] 输出: "fl" 示例 2: 输入: ["dog","racecar","car"] 输出: "" 解释: 输入不存在公共前缀。 说明:所有输入只包含小写字母 a-z 。

2. 提交记录

3. 算法思想

当字符串的长度 strsSize 为 0 时，返回空串； 当字符串的长度 strsSize 为 1 时，返回该字符串； 当字符串的长度 strsSize 大于1时，比较第一和第二个字符串的长度，取较小的一个作为循环次数。如果字符串char ** strs当中有空串，直接返回空串 “” 不再进行比较查找。

4. 代码实现

char * longestCommonPrefix(char ** strs, int strsSize){ /* * 思路： * 先比较第一和第二个，如果有公共的前缀，则用前缀和第三个比较 * 如果没有公共前缀，就直接返回""，后面的不需要比较. */ char * str = (char *)malloc(128 * sizeof(char)); //用来存储公共前缀 memset(str, 0, 128); if (strsSize == 0 ) { return ""; } strcpy(str, strs[0]); if(strsSize == 1){ return str; } int len = strlen(str); //用来计算公共前缀的长度 if(len > strlen(strs[1])){ len = strlen(strs[1]); } for (int i = 1; i < strsSize; i++) { if(strlen(strs[i]) == 0){ return ""; } char * currentStr = strs[i]; int j; for (j = 0; j < len; j++) { if (str[j] != currentStr[j]) { break; } } len = j; str[j] = '\0'; } return str; }