​LeetCode刷题实战14: 最长公共前缀

算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试。所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 !

今天和大家聊的问题叫做最长公共前缀 ,我们先来看题面:

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"]
输出: ""
解释: 输入不存在公共前缀。

题解

解法一

这种解法是暴力循环法,从题目可知:最长公共前缀的最长长度一定是字符串数组中长度最短哪个字符串。
  1. 首先找出长度最短的字符串str,加入str="abcf"。

  2. 依次对'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;
}

解法三

利用二分法的思想
  1. 找出最短的字符串记为m;

  2. 对字符串m进行二分,分割点记为mid,用tmp表示m[low...high]。

  3. 如果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;
}

今天的文章就到这里,如果觉得有所收获,请顺手点个在看或者转发吧,你们的支持是我最大的动力。

上期推文:

LeetCode刷题实战1:在数组上遍历出花样

LeetCode刷题实战2:用链表模拟加法

LeetCode刷题实战3:最长不重复子串

LeetCode刷题实战4:两个正序数组的中位数

LeetCode刷题实战5:判断回文子串

LeetCode刷题实战6:Z字形变换

LeetCode刷题实战7:整数反转

LeetCode刷题实战8:字符串转换整数

LeetCode刷题实战9:求解回文数

LeetCode刷题实战10:字符串正则匹配

LeetCode刷题实战11: 盛最多水的容器

LeetCode刷题实战12: 整数转罗马数字

LeetCode刷题实战13: 罗马数字转整数

(0)

相关推荐

  • # 02 公共前缀问题

    A 思想 前缀: 对题目所给数组进行排序(Array.sort) 设立一个哨兵字符,默认为false(用来判断是否有必要遍历下去) 设置字符串str,默认为""(来拼接每次遍历得到 ...

  • LeetCode之Longest Common Prefix

    LeetCode之Longest Common Prefix

  • 详解最长公共子序列问题,秒杀三道动态规划题目

    作者:labuladong 公众号:labuladong 读完本文,可以去力扣解决如下题目: 1143.最长公共子序列(Medium) 583. 两个字符串的删除操作(Medium) 712.两个字符 ...

  • ​LeetCode刷题实战236:二叉树的最近公共祖先

    算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试.所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 ! 今天和大家 ...

  • ​LeetCode刷题实战235:二叉搜索树的最近公共祖先

    算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试.所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 ! 今天和大家 ...

  • ​LeetCode刷题实战298:二叉树最长连续序列

    算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试.所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 ! 今天和大家 ...

  • ​LeetCode刷题实战128:最长连续序列

    算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试.所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 ! 今天和大家 ...

  • ​LeetCode刷题实战409:最长回文串

    算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试.所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 ! 今天和大家 ...

  • ​LeetCode刷题实战424:替换后的最长重复字符

    算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试.所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 ! 今天和大家 ...

  • ​LeetCode刷题实战260:只出现一次的数字 III

    算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试.所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 ! 今天和大家 ...

  • ​LeetCode刷题实战258:各位相加

    算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试.所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 ! 今天和大家 ...

  • ​LeetCode刷题实战257:二叉树的所有路径

    算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试.所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 ! 今天和大家 ...