Java教程

算法-最长公共前缀

本文主要是介绍算法-最长公共前缀,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

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"}

这篇关于算法-最长公共前缀的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!