c语言字符串最长前缀,14.最长公共前缀（LeetCode）——C语言

方法一、横向遍历法// 横向遍历法

#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));

}

时间复杂度：O(mn)，其中m是字符串数组中的字符串的平均长度，n 是字符串的数量。最坏情况下，字符串数组中的每个字符串的每个字符都会被比较一次。

空间复杂度：O(1)。使用的额外空间复杂度为常数。

方法二、纵向遍历法// 纵向遍历法

#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));

}

时间复杂度：O(mn)，m是字符串数组中的字符串的平均长度，n是字符串的数量。最坏情况下，字符串数组中的每个字符串的每个字符都会被比较一次。

空间复杂度：O(1)。使用的额外空间复杂度为常数。

方法三、分治法// 分治法

#include

#include

#include

char *commonPrefix(char *leftStr, char *rightStr)

{

int len = strlen(leftStr) < strlen(rightStr) ? strlen(leftStr) : strlen(rightStr);

char *str = (char *)malloc((len + 1) * sizeof(char));

memset(str, '\0', len + 1);

for (int i = 0; i < len; i++)

{

if (leftStr[i] != rightStr[i])

{

strncpy(str, leftStr, i);

return str;

}

}

strncpy(str, leftStr, len);

return str;

}

char *recurse(char **strs, int start, int end)

{

if (start == end)

{

return strs[start];

}

int mid = (end - start) / 2 + start;

char *leftStr = recurse(strs, start, mid);

char *rightStr = recurse(strs, mid + 1, end);

return commonPrefix(leftStr, rightStr);

}

char *longestCommonPrefix(char **strs, int strsSize)

{

if (strsSize <= 0)

{

return "";

}

return recurse(strs, 0, strsSize - 1);

}

int main(void)

{

char *strs[] = {"dog", "racecar", "car"};

printf("%s\n", longestCommonPrefix(strs, 3));

}

时间复杂度：O(mn)，其中m是字符串数组中的字符串的平均长度，n是字符串的数量。时间复杂度的递推式是T(n)=2⋅T(2n)+O(m)，通过计算可得T(n)=O(mn)。

空间复杂度：O(mlogn)，其中m是字符串数组中的字符串的平均长度，n是字符串的数量。空间复杂度主要取决于递归调用的层数，层数最大为logn，每层需要m的空间存储返回结果。

方法四、二分查找// 二分查找

#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));

}

时间复杂度：O(mnlogm)，其中m是字符串数组中的字符串的最小长度，n是字符串的数量。二分查找的迭代执行次数是O(logm)，每次迭代最多需要比较mn个字符，因此总时间复杂度是O(mnlogm)。

空间复杂度：O(1)。使用的额外空间复杂度为常数。