MENU

每日一刷:最长公共前缀

• June 15, 2020 • Read: 40 • Note,算法题

题目来源于leetcode,每日一刷小算法。

不管遇到什么挫折,明天的太阳都会照样升起

题目

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

如果不存在公共前缀,返回空字符串 ""。

示例1

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

示例2

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

说明

所有输入只包含小写字母 a-z 。

思路

暴力解法

首先使用for循环让数组遍历。在这个循环中,让每个字符串里面的字符一一对比,直到对比到不相同的字符就退出。然后在这个不同的位置上切割,把前面相同的部分取出来。把取出来的这部分拿到跟下一个字符串对比。

例如:["lexinhu","lexinw","lexi"]

让前两个字符串中两个字符一一对比(可以用到while循环),到h和w这两个不同的位置时跳出循环,截取lexin,让lexin与lexi对比,截取到lexi,返回lexi即可。

Java自带的方法

针对上面的思路,我们可以用Java-String中的startWith()方法,判断第二个字符串是否以第一个字符串开头,如果不是,让第一个字符串裁剪掉一个尾部字符,继续对比。

例如:["lexinhu","lexinw","lexi"]

使用lexinhu与lexinw对比,不同时,lexinhu裁剪掉u,剩下lexinh,继续对比,直到lexin,刚好lexinw是以这个开头的,此时这个公共部门就是lexin,跟第三个字符lexi对比,执行相同的操作。

代码实现

暴力解

class Solution {
    public String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0) {
            return "";
        }
        String s = strs[0];
        for (int i = 1; i < strs.length; i++) {
            int index = 0;
            while (
                    index < (Math.min(s.length(),strs[i].length()))
                    && s.charAt(index) == strs[i].charAt(index)
            ){
                index++; 
            }
            s = strs[i].substring(0, index);
            if(s.length() == 0){
                return s;
            }
        }
        return s;
    }
}

优化后

class Solution {
    public String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0) {
            return "";
        }
        String s = strs[0];
        for (int i = 1; i < strs.length; i++) {
            while(!strs[i].startsWith(s)){
                s = s.substring(0, s.length()-1);
            }
        }
        return s;
    }
}

本站所有未注明转载的文章均为原创,并采用CC BY-NV-SA 4.0 授权协议,转载请注明来源。

Archives QR Code
QR Code for this page
Tipping QR Code