今天和大家聊的问题叫做最长公共前缀 ，我们先来看题面：
https://leetcode-cn.com/problems/longest-common-prefix/
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 "".
题意
编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀，返回空字符串 ""。
样例
示例 1: 输入: ["flower","flow","flight"] 输出: "fl" 示例 2: 输入: ["dog","racecar","car"] 输出: "" 解释: 输入不存在公共前缀。
题解
解法一
这种解法是暴力循环法，从题目可知：最长公共前缀的最长长度一定是字符串数组中长度最短哪个字符串。
- 首先找出长度最短的字符串str，加入str="abcf"。
- 依次对'abcf'、'abc'、'ab'、'a'进行筛选，判断哪个是所有其他字符串的前缀。
public String longestCommontPrefix6(String[] strs) { if(strs.length == 0) { return ""; } int min = Integer.MAX_VALUE; for(String str : strs) { min = Math.min(min, str.length()); } int low = 1; int high = min; while(low <= high) { int middle = (low + high)/2; if(this.isCommontPrefix(strs, middle)) { low = middle + 1; } else { high = middle - 1; } } return strs[0].substring(0, (low + high)/2); } public boolean isCommontPrefix(String[] strs, int length) { String tmp = strs[0].substring(0, length); for (int i=0; i<strs.length; i++) { if(!strs[i].startsWith(tmp)) { return false; } } return true; }
解法二
这种方法称之为水平扫描法，用一张图来表示其具体过程如下：
首先假设最长前缀result=str[0], 遍历字符串数组，依次与result做比较，找出其最长前缀，然后更新result，再进行下一次比较。
public String longestCommonPrefix3(String[] strs) { if(strs.length == 0) { return ""; } String result = strs[0]; for(int i=0; i<strs.length; i++) { while(strs[i].indexOf(result) != 0) { result = result.substring(0, result.length()-1); if(result.length() == 0) { return ""; } } } return result; }
解法三
利用二分法的思想
- 找出最短的字符串记为m;
- 对字符串m进行二分,分割点记为mid，用tmp表示m[low...high]。
- 如果tmp为所有字符串的前缀，则mid右移，否则左移，直到low>high。
代码如下：
public String longestCommontPrefix6(String[] strs) { if(strs.length == 0) { return ""; } int min = Integer.MAX_VALUE; for(String str : strs) { min = Math.min(min, str.length()); } int low = 1; int high = min; while(low <= high) { int middle = (low + high)/2; if(this.isCommontPrefix(strs, middle)) { low = middle + 1; } else { high = middle - 1; } } return strs[0].substring(0, (low + high)/2); } public boolean isCommontPrefix(String[] strs, int length) { String tmp = strs[0].substring(0, length); for (int i=0; i<strs.length; i++) { if(!strs[i].startsWith(tmp)) { return false; } } return true; }
今天的文章就到这里，如果觉得有所收获，请顺手点个在看或者转发吧，你们的支持是我最大的动力。
