办法一、横向遍历法
// 横向遍历法#include <stdio.h>#include <string.h>#include <stdlib.h>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 <stdio.h>#include <stdlib.h>#include <string.h>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 <stdio.h>#include <stdlib.h>#include <string.h>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));}