关于c:14最长公共前缀LeetCodeC语言

办法一、横向遍历法

// 横向遍历法
#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));
}