题目
编写一个函数来查找字符串数组中的最长公共前缀
如果不存在公共前缀,返回空字符串 ""
规则示例
规则:
1 <= strs.length <= 200
0 <= strs.length <= 200
strs[ i ] 仅由小写英文字母组成
示例1:
输入:strs = [“flower”,“flow”,“flight”]
输出:“fl”
示例2:
输入:strs = [“dog”,“racecar”,“car”]
输出:""解释:输入不存在公共前缀。
解题分析一:纵向比较
纵向比较是一个比较符合人思维的比较方式
我们取出第一个字符串,然后遍历它的每个字符
用得到的字符和数组后面的字符串的对应位置进行比较
我们以数组 [“flower”,“flow”,“flight”] 为例
我们取出 flower 用来遍历
第一次
第二次
第三次:结束
解题一:纵向比较
解题分析二:横向比较
横向比较的主要思路是逐个比较字符串
得到两个字符串之间的最长公共前缀
再用该公共前缀和下一个字符串比较,以此类推
解题二:横向比较
解题分析三:分治法
在计算机科学中,分治法是一种很重要的算法。
字面上的解释是“分而治之”,就是把一个复杂的问题分成两个或更多的相同或相似的子问题,再把子问题分成更小的子问题,直到最后子问题可以简单的直接求解,原问题的解即子问题的解的合并
比如:快速排序、归并排序等算法都是用的分治法
分治与函数递归像一对孪生兄弟,经常同时应用在算法设计之中
分治法中每一层递归上都有三个步骤:
分解:将原问题分解为若干个规模较小,相互独立,与原问题形式相同的子问题
解决:若子问题规模较小而容易被解决则直接解,否则递归地解各个子问题
合并:将各个子问题的解合并为原问题的解
我们把字符串数组不停的进行递归拆分
直到拆分成单个字符串时才开始进行比较
解题三:分治法
递归对于很多同学来说是逻辑难点,理清递归思路最简单的方式就是在草稿纸上整理递归函数的执行逻辑,当掌握了递归的套路后,解决递归相关算法题的能力自然就能得到提升。
总结
这道“最长公共前缀”是一道较为简单的题目,但是它的解法有很多种。除了我们上面讲解的三种方法,还有一种常见的利用二分查找来解该题的方案。大家可以自己尝试使用二分查找来解决该题目,可以把答案写在留言区,分享给大家~
END