算法-最长公共前缀
2022/7/30 1:25:26
本文主要是介绍算法-最长公共前缀,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
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"}
这篇关于算法-最长公共前缀的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-04-26敏捷开发:想要快速交付就必须舍弃产品质量?
- 2024-04-26静态代码分析的这些好处,我竟然都不知道?
- 2024-04-26你在测试金字塔的哪一层?(下)
- 2024-04-26快刀斩乱麻,DevOps让代码评审也自动起来
- 2024-04-262024年最好用的10款ER图神器!
- 2024-04-2203-为啥大模型LLM还没能完全替代你?
- 2024-04-2101-大语言模型发展
- 2024-04-17基于SpringWeb MultipartFile文件上传、下载功能
- 2024-04-14个人开发者,Spring Boot 项目如何部署
- 2024-04-14RAG应用开发实战02-相似性检索的关键 - Embedding