方法一、横向遍历法
// 横向遍历法
#include
#include
#include
int getCommonPrefix(char *prev, char *next) {
int len = strlen(prev) < strlen(next) ? strlen(prev) : strlen(next);
int k = 0;
while (k < len) {
if (prev[k] != next[k]) {
return k;
}
k++;
}
return k;
}char *longestCommonPrefix(char **strs, int strsSize) {
if (strsSize <= 0) {
return "";
}
int commonPrefixLen = strlen(strs[0]);
char *commonPrefix = (char *)malloc((commonPrefixLen + 1) * sizeof(char));
strncpy(commonPrefix, *strs, commonPrefixLen);
// 给字符串结尾加上空字符，否则会数组访问出错，导致堆溢出
// 这个问题找了好久，最后发现strncpy只是复制字符，并不会自动在字符串结尾添加空字符
*(commonPrefix + commonPrefixLen) = '\0';
for (int i = 1;
i < strsSize;
i++)
{
int len = getCommonPrefix(commonPrefix, *(strs + i));
// 将字符串初始化为全空，此后复制字符不用担心结尾添加空字符的问题
memset(commonPrefix, '\0', commonPrefixLen + 1);
if (len <= 0) {
return commonPrefix;
}
strncpy(commonPrefix, *(strs + i), len);
}
return commonPrefix;
}int main(void) {
char *strs[] = {"flower", "flow", "flight"};
printf("%s\n", longestCommonPrefix(strs, 3));
}
文章图片
方法二、纵向遍历法
// 纵向遍历法
#include
#include
#include char *longestCommonPrefix(char **strs, int strsSize)
{
if (strsSize <= 0) {
return "";
}
int len = strlen(strs[0]);
char *commonPrefix = (char *)malloc((len + 1) * sizeof(char));
memset(commonPrefix, '\0', len + 1);
for (int i = 0;
i < len;
i++)
{
for (int j = 0;
j < strsSize - 1;
j++) {
// i == strlen(strs[j])用来防止数组访问越界
if (i == strlen(strs[j]) || strs[j][i] != strs[j + 1][i])
{
strncpy(commonPrefix, strs[0], i);
return commonPrefix;
}
}
}
return strs[0];
}int main(void) {
char *strs[] = {"flower","flow","flight"};
printf("%s\n", longestCommonPrefix(strs, 3));
}
文章图片
方法四、二分查找
// 二分查找
#include
#include
#include int getMinLen(char **strs, int strsSize)
{
int minLen = strlen(strs[0]);
for (int i = 1;
i < strsSize;
i++) {
if (strlen(strs[i]) < minLen)
{
minLen = strlen(strs[i]);
}
}
return minLen;
}int isCommonPrefix(char **strs, int strsSize, int mid) {
for (int i = 0;
i < strsSize - 1;
i++) {
if (strncmp(strs[i], strs[i + 1], mid) != 0) {
return 0;
}
}
return 1;
}char *longestCommonPrefix(char **strs, int strsSize)
{
if (strsSize <= 0) {
return "";
}
int minLen = getMinLen(strs, strsSize);
char *commonPrefix = (char *)malloc((minLen + 1) * sizeof(char));
memset(commonPrefix, '\0', minLen + 1);
int left = 1;
int right = minLen;
while (left <= right) {
int mid = (left + right) / 2;
if (isCommonPrefix(strs, strsSize, mid))
{
left = mid + 1;
} else {
right = mid - 1;
}
}
strncpy(commonPrefix, strs[0], right);
return commonPrefix;
}int main(void)
{
char *strs[] = {"flower", "flow", "flight"};
printf("%s\n", longestCommonPrefix(strs, 3));
}【14.最长公共前缀（LeetCode）——C语言】
文章图片
