编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀,则返回""【leetcode】
输入: ["flower","flow","flight"] 输出: "fl"
输入: ["dog","racecar","car"] 输出: ""
解释:输入不存在公共前缀。
假定我们现在就从一个数组中寻找最长公共前缀,那么首先,我们可以将第一个元素设置为基准元素x0。假如数组为["flow","flower","flight"],flow就是我们的基准元素base。然后我们只需要依次将基准元素和后面的元素进行比较(假定后面的元素依次为s1,s2,s3....),不断更新基准元素,直到基准元素和所有元素都满足最长公共前缀的条件,就可以得到最长公共前缀。
具体比对过程如下:
先申请一块地址空间commonPrefix,大小是第一个字符串的大小+1,并全置为'\0'。依次将si与base逐个字母比较,当不等时候,将相等部分拷贝到commonPrefix,然后更新bese,最后就是想要的结果(一开始base=flower,flower和flow比较,然后base更新为flow,然后用这个base和s2比较,以此类推)
我们需要注意的是,在处理基准元素的过程中,如果基准元素和任一一个元素无法匹配,则说明不存在最长公共元素。最后,我们记得处理一下临界条件。如果给定数组是空,也说明没有最长公共元素。
先申请一块地址空间,大小是第一个字符串的大小+1,并全置为'\0'。纵向扫描时,从前往后遍历所有字符串的每一列,比较相同列上的字符是否相同,如果相同则继续对下一列进行比较,如果不相同则当前列不再属于公共前缀,当前列之前的部分为最长公共前缀。
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 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]; }
int strsLen = 3 char* strs[strsLen] = {"flow","flower", "flight"}