横向扫描教你搞定“最长公共前缀”问题

• 一、前言
• 二、最长公共前缀
• • 1.题意
  • 2.示例
  • 3.题解
  • • 横向扫描
    • • 思路分析
      • 代码解析
      • • C语言代码解析及详细注释说明
        • python代码解析及详细注释说明
        • Java代码解析及详细注释说明
• 三、反思总结
• • 反思
  • 总结

昨天做了leetcode上简单等级的14.最长公共前缀问题，今天来做个小结，主要是针对横向扫描算法进行展开分析。

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

示例 1：
输入：strs = [“flower”,“flow”,“flight”]
输出：“fl”

示例 2：
输入：strs = [“dog”,“racecar”,“car”]
输出：""
解释：输入不存在公共前缀。

横向扫描图解：
横向扫描的大致思路简单来说，首先确定字符串数组内字符的最短长度minlen，最长公共前缀的长度不大于该最短长度，接着只需依次遍历字符串数组中的每个字符串的前minlen位，两两之间查找公共字符串，更新最长公共前缀，再用最新的最长公共前缀继续依次往后遍历扫描匹配，当遍历完所有的字符串之后，就能得到最长公共前缀。当然，如果在没有遍历完所有字符串之前，所更新的最长字符串已经是空串了，则无需再往后继续遍历，直接返回空串即可。

代码是自思自写的哈，救命！！！折腾了我好久，终于成功执行啦！现在回头看当时整整提交了30次，一直到第31次才成功。报错的原因主要有三种：
①代码设计不够周全，没有想到strsSize=1的情况，以致于如果运行实例中字符串数组长度只有1的话，会输出空，而不是输出第一个字符串。根据报错信息将代码进行调整，成功解决

else if(strsSize == 1)
return strs[0];

②在横向扫描两层遍历的过程中没有考虑到当字符串数组中的两个字符串中的第一个字符在比较时就发现不相等时，应该立即返回“”，而只是在判断某个字符不等时就返回result，没想到这样可能会导致下面这种情况的出现：

示例：[“fa”,“fa”,""]
输出：[“fa”]

最后在第二层for循环体内的if(strs[i][j] != strs[0][j])中增加判断条件，即可解决这个问题：

for(j = 0; j < minlen; j++)
{
if(strs[i][j] != strs[0][j])
{ if(j == 0)
return “”;
break;
}

③执行不停出错，报错信息为==【ERROR:AddressSanitizer:heap-buffer-overflow on address 0x602000000272 at pc ……】，也有到网上去查过报出此类出错信息可能是什么错误导致的，发现有可能是由于数组下标溢出==导致的，仔细检查横向扫描部分的代码：在我的代码设计中有一块是这样设计的：当两个字符串进行匹配，除第一个字符串就匹配失败的情况以外，一旦中途出现字符匹配失败，就更新最短字符串长度为匹配失败的字符索引值j+1。后面发现应该更新为j而不是j+1，怀疑数组溢出就是指的这，结果更改之后，仍然报错且报错信息一致。
就在我想放弃的时候，想着最后再修改一次，就这样成功啦！主要是将原先条件判断strs[i][j] != strs[0][j]内j != 0的return删除，改为了break。之所以这样改是因为如果不考虑字符串还没有遍历完成就返回result，这样势必会出错。最后更改过后，代码执行成功

for(int i = 1; i < strsSize; i++)
{
for(j = 0; j < minlen; j++)
{
if(strs[i][j] != strs[0][j])
{ if(j == 0)
return “”;
break;
}
result[j] = strs[0][j];
result[j+1] = ‘’;
}
minlen = j;
}
return result;

//最长公共前缀功能函数
char * longestCommonPrefix(char ** strs, int strsSize){
    if(!strsSize)//字符串数组长度为0，返回""空串
        return "";
    else if(strsSize == 1)//字符串数组长度为1，返回第一个字符串
        return strs[0];
    else//字符串数组长度>=1
    {
      	int minlen = strlen(strs[0]);//初始化设置第一个字符串的长度为最短长度
        for(int k = 1; k < strsSize; k++)//遍历字符串数组中的所有字符串，找到最短字符串的长度
        {
            if(minlen > strlen(strs[k]))
            {
                minlen = strlen(strs[k]);
            }
        }
        char * result = (char *)malloc(sizeof(char) * (minlen + 1));//为返回的字符串指针变量申请空间
        result[0] = '';//由于char*字符串要以''结尾，所以初始化result[0]为''
        int j;
        for(int i = 1; i < strsSize; i++)//横向扫描遍历
        {
            for(j = 0; j < minlen; j++)
            {
                if(strs[i][j] != strs[0][j])//如果扫描到的两个字符串中出现对应位上的字符不匹配
                {   if(j == 0)//如果对应的索引值j为0
                        return "";//则无需再往下继续遍历，直接返回空串
                    break;//否则跳出循环
                }
                //如果扫描到的两个字符串出现公共前缀
                //result字符串内存放的字符在遍历过程中持续更新
                result[j] = strs[0][j];//将成功匹配的公共前缀字符串依次存放进result中
                result[j+1] = '';//char*字符串需要以''结尾
            }
            minlen = j;//如果在字符索引值不为0时，字符匹配不成功，则跳出循环，将最短字符串长度更新，继续遍历
        }
        return result;//全部遍历完成之后，返回最终的result，也即最长公共前缀
    }
}

class Solution(object):
    def longestCommonPrefix(self, strs):
        """
        :type strs: List[str]
        :rtype: str
        """
        if not strs:#如果字符串数组strs为空，返回空串
            return ""
        #初始化prefix为第一个字符串，count为字符串数组strs的长度
        prefix, count = strs[0], len(strs)
        #扫描两个字符串并返回它们的最长公共前缀
        def lcp(str1, str2):
            #初始化length为字符串str1和str2比较后的最短长度,index为字符索引
            length, index = min(len(str1), len(str2)), 0
            #当字符索引不超过最短长度且两字符串出现公共前缀时，执行索引+1
            while index < length and str1[index] == str2[index]:
                index += 1
            #否则,截取字符串中0~(index-1)部分的字符
            return str1[:index]
        #横向扫描，依次遍历
        for i in range(1, count):
            prefix = lcp(prefix, strs[i])#不断更新最长公共前缀
            #如果最长公共前缀为空串
            if not prefix:
                break#跳出循环，返回空串
        return prefix#全部扫描完成后，返回最终的最长公共前缀

之前没有用java代码写过算法，我打算从今天开始熟悉在leetcode上用java代码编写算法，请大家监督

class Solution {
    public String longestCommonPrefix(String[] strs) {
    	//如果字符串数组为空，返回空串
        if(strs == null || strs.length == 0)
            return "";
        String prefix = strs[0];
        int count = strs.length;
        for(int i = 1; i < count; i++)
        {
        	//不断遍历扫描更新最长公共前缀
            prefix = longestCommonPrefix(prefix, strs[i]);
            //如果最长公共前缀长度为0，跳出循环，返回空串
            if(prefix.length() == 0)
                break;
        }
        return prefix;
    }
    public String longestCommonPrefix(String str1, String str2)
    {
        int length = Math.min(str1.length(), str2.length());
        int index = 0;
        while(index < length && str1.charAt(index) == str2.charAt(index))
            index++;
        return str1.substring(0, index);//截取公共前缀字符串
    }
}

通过反思自己在采用横向扫描方式求解“最长公共前缀”问题过程中遇到的问题，我意识到自己目前主要欠缺的是：逻辑思维方式不够开阔，经常因为没有考虑到某种情况的出现而导致出错。

同时我也学会了不少的知识：
①在执行代码过程中出现报错信息【ERROR:AddressSanitizer:heap-buffer-overflow on address 0x602000000272 at pc ……】的原因可能是数组溢出或者返回值异常等等。
②char *字符串必须要以’’结尾，所以在代码书写的过程中我们就要格外注意这一点
③在使用同一算法不同语言解题时，我们可以发现C语言的用时和内存消耗都是最小的，但是它也有缺点，就是实现思路比其他两种语言会更复杂一些，最显著地表现在截取最长公共前缀字符串的功能实现上，python语言和java语言实现此功能都只需要使用自带的字符串操作的函数，而在C语言中实现相关功能则需要通过条件判断将匹配成功的字符依次存放到数组中，再遍历扫描更新才行。
④学会了java类中的两种实现字符串操作的方法：
1.Java substring()方法：substring()方法用于返回字符串的子字符串。

语法：public String substring(int beginIndex) public String substring(int
beginIndex, int endIndex) 参数：beginIndex——起始索引（包括），索引从0开始
endIndex——结束索引（不包括）

2.Java charAt()方法：charAt()方法用于返回指定索引处的字符，索引范围为0~length()-1

语法：public char charAt(int index)
参数：index——字符索引
返回值：返回指定索引处的字符

最后我想说，通过这次刷题经历，我深刻认识到有时候只要我们再坚持一下下，就能出现结果。之后还会继续更新“最长公共前缀”问题的其他解法，每天记录一点点，收获亿点点！
2021.10.18突破：第一次尝试用java语言编写算法题✌