算法-最长公共前缀

• 2022 年 7 月 29 日
• 笔记
• leetcode, 数组, 算法

01、题目分析

编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀，则返回””【leetcode】

示例1

输入: ["flower","flow","flight"]
输出: "fl"

示例2

输入: ["dog","racecar","car"]
输出: ""

解释：输入不存在公共前缀。

02、题解分析

方法1

假定我们现在就从一个数组中寻找最长公共前缀，那么首先，我们可以将第一个元素设置为基准元素x0。假如数组为[“flow”,”flower”,”flight”]，flow就是我们的基准元素base。然后我们只需要依次将基准元素和后面的元素进行比较（假定后面的元素依次为s1,s2,s3….），不断更新基准元素，直到基准元素和所有元素都满足最长公共前缀的条件，就可以得到最长公共前缀。
具体比对过程如下：
先申请一块地址空间commonPrefix，大小是第一个字符串的大小+1，并全置为’\0’。依次将si与base逐个字母比较，当不等时候，将相等部分拷贝到commonPrefix，然后更新bese，最后就是想要的结果（一开始base=flower，flower和flow比较，然后base更新为flow，然后用这个base和s2比较，以此类推）

我们需要注意的是，在处理基准元素的过程中，如果基准元素和任一一个元素无法匹配，则说明不存在最长公共元素。最后，我们记得处理一下临界条件。如果给定数组是空，也说明没有最长公共元素。

方法2

先申请一块地址空间，大小是第一个字符串的大小+1，并全置为’\0’。纵向扫描时，从前往后遍历所有字符串的每一列，比较相同列上的字符是否相同，如果相同则继续对下一列进行比较，如果不相同则当前列不再属于公共前缀，当前列之前的部分为最长公共前缀。

初始状态

结束状态

03、题解

方法1

char* longestCommonPrefix(char** strs, int strsLen ) {
  if (strsLen == 0)
    return "";

  if (strsLen == 1)
    return *strs;

  int i, j, k;
  char* base = strs[0];

  char* commonPrefix = (char*)malloc((strlen(base) + 1) * sizeof(char));
  memset(commonPrefix, '\0', strlen(base) + 1);

  for (i = 1; i < strsLen; i++) {
    // j 指向每个字母
    for (j = 0; j < strlen(base); j++) {
      if (strs[i][j] != base[j]) {
        strncpy(commonPrefix, base, j);
          for (k = j; k < strlen(commonPrefix); k++){
            commonPrefix[k] = '\0';
          }
          base = commonPrefix;
      }
    }
  }
  return base;
}

方法2

// 方法2
char * longestCommonPrefix(char ** strs, int strsSize){
  if(strsSize == 0)
    return "";

  if(strsSize == 1)
    return *strs;
  
  //申请7个字符，最后一个存放 '\0' 
  char *commonPrefix = (char *)malloc((strlen(strs[0]) + 1) * sizeof(char)); 
  memset(commonPrefix, '\0', strlen(strs[0]) + 1);  

  int i,j;

  // i分别指向每一个字母  
  for (i = 0; i < strlen(strs[0]); i++) {
    // j 指向每一个单词 
    char c = strs[0][i];
    for(j = 0; j < strsSize; j++) {
      if(strs[j][i] != c) {
           strncpy(commonPrefix, strs[0], i);
           return commonPrefix;
        }   
    }
  }
  return strs[0];
}

04、测试结果

  int strsLen = 3
  char* strs[strsLen] = {"flow","flower", "flight"}