本文共 4967 字，大约阅读时间需要 16 分钟。

题目描述

Write a function to find the longest common prefix string amongst an array of strings.

写一个函数，找到一个字符串数组中的最长的共有的前缀

If there is no common prefix, return an empty string “”.

如果没有公共前缀，返回一个空的字符串“”

Example 1:

Input: ["flower","flow","flight"] Output: "fl"

Example 2:

Input: ["dog","racecar","car"] Output: "" Explanation: There is no common prefix among the input strings.

Note:

All given inputs are in lowercase letters a-z.

所有的输入字符都是由a-z的26个小写字母构成

思路分析

方法一：逐个字符进行比对

• 从第一个字符串开始，遍历第一个字符串的每一个字符，然后在和后面所有的字符串对应的位置的字母进行比较。同则继续迭代；不同就退出。
  • 小问题：如何容纳最终的结果：
    • 创建和第一个字符一样长的字符数组。

方法二：调用字符串直接进行字符串整体比较运算。

• 先是整体进行比较。结果为0，说明二者相同；结果为非零，说明二者不相同。
• 不同的情况下，向下折半，相同就向上折半。
• 知识点补充：
  • strncmp（字符串1，字符串2，比较的字符串的数目n），比较两个字符串从零到n个字符的大小。结果为正，前面的字符大；结果为负，后面的字符串大；结果为零，两者相等。
    

代码实现

brute force（暴力法）——占内存，耗时间，不建议采用

#include 
   
    #include 
    
     #include 
     
      char *longestCommonPrefix(char **strs, int sresSize);int main(){
       //今日份leetcode    char *str1[] = {
   ""};    printf("%s \n",longestCommonPrefix(str1,1));    return 0;}/*    功能描述：获取所有的字符串的最长的公共子串*/char *longestCommonPrefix(char ** strs, int strsSize){
       //创建一个和第一个字符串等长的内存空间    char *result = NULL;    result = (char *)malloc(sizeof(strs[0])+1);    if(!result)    {
           printf("申请内存失败");        return NULL;    }    memset(result,0,sizeof(strs[1]) + 1);    //从第一个字符串开始遍历    for(int i = 0;i < strlen(strs[0]);i ++)    {
           for(int j = 1;j < strsSize;j ++)        {
               if(strs[0][i] != strs[j][i] && i < strlen(strs[j]))            {
                   goto end;            }        }        result[i] = strs[0][i];    }end:    return result;}
     
    
   

折半查找法

int IterateStrcmp(char **strs,int strsSize,int middle){
       int temp = 0;    for(int i = 1;i < strsSize;i ++)    {
           temp = strncmp(strs[0],strs[i],middle);        if(temp)        {
               break;        }    }    return temp;}/*    功能描述：采用折半比较法，来快速判定*/char *longestCommonPrefix(char **strs, int strsSize){
       //排除空数组的情况    if(strsSize < 1)    {
           return "";    }    //单个数组直接返回    if(strsSize == 1)    {
           return strs[0];    }    //    int end = strlen(strs[0]), temp = 0;    for(int i = 1;i < strsSize;i ++)    {
           temp = strlen(strs[i]);        if(end > temp)        {
               end = temp;        }    }    int start = 0, middle = end;    while(1)    {
           if(!IterateStrcmp(strs,strsSize,middle))        {
               if((IterateStrcmp(strs,strsSize,middle + 1) || middle == start)||(middle == end))            {
                   break;            }            else            {
                   start = middle;            }        }        else        {
               end = middle;        }        middle = (start + end) / 2;    }    //创建一个和第一个字符串等长的内存空间    char *result = NULL;    result = (char *)malloc(middle * sizeof(char)+1);    if(!result)    {
           printf("申请内存失败");        return NULL;    }    memset(result,0,middle * sizeof(char)+1);    strncpy(result,strs[0],middle);    return result;}

关于char **和字符串的一些浅显的认知

• char **strs：C语言学的比较水，这个含义没看懂。其实就是char * [ ]的意思。数组和指针可以互换使用，一维数组为例，int a[] 可以用a来代表指针，这样获取数组元素*a

char *str1[] = {
   "asdf","asder","asdcv","asdwe","asdfgh"};

• 关于字符串数组的总结：
  • char *strs[]:
    • 数组名strs，表示指向第一个字符串的指针的地址，要获取字符串的指针还需要进行解引用计算
    • *strs 等价于strs[0]
    • *(strs+1) 等价于strs[0]
  • char **strs:
    • 可以用这种方式声明字符串数组，用来做字符串数组的形参表示，但是传入的实际上是以char *[]声明的字符串数组

• char **p的使用注意：
  • 当有如下的声明时，p仅仅指向第一个字符串的地址。而且在存储字符串常量的静态存储区仅仅有第一个字符串“asdfll”，后面的字符串都没有写入其中。
  • 对P进行-/+1，并不能指向下一个字符串，本质上是在原先的地址上加上一个指针变量的长度，64位操作系统的指针就是8个字节，就是加8
  • 指针变量的字节数取决于操作系统的所能操作的位数。32位机，就是有4个字节，一个字节八位

char **strs = {
   "asdfll","asder","asdcv","asdwe","asdfgh"};

• 如何将char型的字符和char *型的字符串连接起来。
  • char *p[] = {},字符串该用数组的调用方式，p[x]单个调用其中一个字符返回。
  • 字符串之间的连接，用strcat函数，strcat（前一个字符串，后一个字符串）；

关于折中查找的一些肤浅认知

• 一定要有两个标志，start和end，才可以进一步确定中间的结点，再往后迭代的迭代的过程中不会出现重复的问题
• 这题跟普通的二分查找不一样。第一次比对应该是以最短的字符串长度为比较的标准，即middle = end，所以迭代条件应该有所修改放到循环提的后面

错误锦集

• runtime error问题1：

* 原因：当输入的数组为“[]”，不带任何的元素，程序将之有效的排除，所以会出现访问越界，增加如下段代码。

char *longestCommonPrefix(char ** strs, int strsSize){
       //排除输入空数组的情况        if(strsSize < 1)    {
           return "";    }        //创建一个和第一个字符串等长的内存空间    char *result = NULL;    result = (char *)malloc(sizeof(strs[0])+1);    if(!result)    {
   ...

• runtime error问题2：

• 问题原因：没有足够的存储空间去存储char型数组。
• 误区：遍历整个数组，后去其中最短的字符串的长度,并不能解决。程序运行的时间过长。同时遍历第一个字符串的每一个字符仍旧不能节省时间，因此直接选出最短的，然后从最短的开始比较。

//找到数组中长度最短的元素    int min = 0;    for(int i = 0;i < strsSize;i ++)    {
           if(strlen(strs[min]) > strlen(strs[i]))        {
               min = i;        }    }

结果：

• 当输入足够长，项数足够多，每条都等长，相同的数组的时候，自动溢出宕机。说明方法不对，更换方法。

借鉴和学习

Horizontal scanning（水平扫描）

• 单体比较优于整体比较，确定了方向只不断往回缩减，不会出现增加的情况。
• 首先比较前两个字符串，确定了前两个字符串的最长字串前缀，再用该最长前缀字串和后面的字符串进行比较，确知道最后的结果。

Vertical Scanning

遍历所有的单词的同一个序号的字母，相同就继续，不同就返回，跟我的暴力破解法相同

Divide and conquer

• 在horitoncal scan水平扫描的基础上，采用递归的方式。将原来的字符串数组对半分，再分，直到分到仅剩唯一的字符串，然后再进行水平扫描，获取最短的公共最长的前缀。
• 归并排序图示

拓展概念

• Trie：称为单词查找树，字典树
• 图示
• 作用：应用于统计，排序和保存大量的字符串，常被用于搜索引擎系统去做文本词频统计
• 优点：利用字符串的公共前缀去减少查询时间，最大限度的减少无谓的字符串的比较

转载地址：http://mggpb.baihongyu.com/