LeetCode-14 最长公共前缀

用户3470542

发布于 2019-06-26 16:18:18

4100

发布于 2019-06-26 16:18:18

文章被收录于专栏：算法半岛算法半岛

↑点击上面"算法半岛"

关注"算法半岛"第一时间接收最新文章

> 题目：14. 最长公共前缀

> 难度：简单

> 分类：字符串

> 解决方案：字符串遍历

今天我们学习第14题最长公共前缀，这是一道简单题。像这样字符串的题目经常作为面试题来考察面试者算法能力和写代码能力，因此最好能手写出该题。下面我们看看这道题的题目描述。

题目描述

编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀，返回空字符串 ""。示例 1:

输入: ["flower","flow","flight"]输出: "fl"

示例 2:

输入: ["dog","racecar","car"]输出: ""解释: 输入不存在公共前缀。

分析

这个题目让我们求字符串数组中的最长公共前缀，我们可以使用第0行的字符串作为基准，与其他剩余的字符串比较来找出最长的公共前缀，示例1分析方法如下图所示：

将上述分析方法转化为 java代码如下所示：

class Solution {    public String longestCommonPrefix(String[] strs) {        StringBuilder res = new StringBuilder();
        if(strs == null || strs.length == 0 )            return  res.toString();
        for (int col = 0; col < strs[0].length(); col++){            // 第0行的第col个字符            char c = strs[0].charAt(col); 
            // 基准字符串中的字符与其他字符串中的字符进行对比            for(int row = 1; row < strs.length; row++){                if(col >= strs[row].length() || strs[row].charAt(col) != c)                    return  res.toString();            }
            res.append(c);        }
        return res.toString();    }}

仔细想想，如果字符串数组按照字符顺序排好序后（可以使用相关语言的排序函数进行排序，排好序后数组中共同字母多的字符串会被放到一起，而共同字符最少的字符串则会被放到首尾两端），我们不需要比较所有的字符串，而只需要比较首字符串和尾字符串即可，用这种排序方法对示例1分析的示意图如所下图所示：

将上述分析方法转化为 java代码如下所示：

class Solution {    public String longestCommonPrefix(String[] strs) {        StringBuilder res = new StringBuilder();
        if(strs == null || strs.length == 0 )            return  res.toString();
        // 将字符串数组排序        Arrays.sort(strs);
        // 取数组中的首尾字符串，并将其转为字符数组        char[] firstRow = strs[0].toCharArray();        char[] lastRow = strs[strs.length-1].toCharArray();
        // 查找公共前缀时只需要查找最短长度的字符串        int len = firstRow.length < lastRow.length ? firstRow.length : lastRow.length;
        // 比较首位两个字符串，取最长公共前缀        for(int i=0; i<len; i++){            if(firstRow[i] != lastRow[i])                return res.toString();            res.append(firstRow[i]);        }        return res.toString();    }}