Day9 最长公共前缀

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

https://leetcode-cn.com/problems/longest-common-prefix/

示例1：

输入：strs = ["flower","flow","flight"]
输出："fl"

示例2：

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

提示：

0 <= strs.length <= 200
0 <= strs[i].length <= 200
strs[i] 仅由小写英文字母组成

Java解法

思路：

  • 简单思路：两两取出公共串，做为新串与下个字符串比较，有公共继续知道比较完成，输出；若无则表示没有公共串

  • 犯二：这里做拆分求两个字符串的公共前缀做成了求公共子串

    public static String getCommon(String s1, String s2) {
        int i = 0;
        List<Character> list = new ArrayList<>();
        String result = "";
        while (i<s1.length()&&i<s2.length()){
            if (s1.charAt(i)==s2.charAt(i)) {
                list.add(s1.charAt(i));
            }else {
                String temp = "";
                for (Character character : list) {
                    temp+=character;
                }
                list.clear();
                result = result.length()>=temp.length()?result:temp;
            }
            i++;
        }
        String temp = "";
        for (Character character : list) {
            temp+=character;
        }
        result = result.length()>=temp.length()?result:temp;
        return result;
    }

package sj.shimmer.algorithm;

/**
 * Created by SJ on 2021/2/2.
 */

class D9 {
    public static void main(String[] args) {
        System.out.println(longestCommonPrefix(new String[]{"flower","flow","flight"}));
        System.out.println(longestCommonPrefix(new String[]{"dog","racecar","car"}));
        System.out.println(longestCommonPrefix(new String[]{"cir","car"}));
        System.out.println(longestCommonPrefix(new String[]{"flower","fkow"}));
    }
    public static String longestCommonPrefix(String[] strs) {
        if (strs==null||strs.length==0) {
            return "";
        }
        String result = strs[0];
        for (int i = 1; i < strs.length; i++) {
            String common = getCommonPre(result, strs[i]);
            if (common!=null&&common!="") {
                result = common;
            }else {
                return "";
            }
        }
        return result;
    }

    public static String getCommonPre(String s1, String s2) {
        int i = 0;
        String result = "";
        while (i<s1.length()&&i<s2.length()){
            if (s1.charAt(i)==s2.charAt(i)) {
                result+=s1.charAt(i);
            }else {
                return result;
            }
            i++;
        }
        return result;
    }
}
image

官方解

  1. 横向扫描

    上方同样的思路,但官方的求公共前缀方法明显更好，计算位置再剪切，提高了大量效率

    public  String getCommonPre(String str1, String str2) {
>        int length = Math.min(str1.length(), str2.length());
>         int index = 0;
>         while (index < length && str1.charAt(index) == str2.charAt(index)) {
>             index++;
>         }
>         return str1.substring(0, index);
>     }
> ```
>
> ![image](https://upload-images.jianshu.io/upload_images/3026588-9c01ffaa07511f4f.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240)
    • 时间复杂度： O(mn)，其中 m是字符串数组中的字符串的平均长度，n是字符串的数量。最坏情况下，字符串数组中的每个字符串的每个字符都会被比较一次
    • 空间复杂度： O(1)。使用的额外空间复杂度为常数

  2. 纵向扫描

    纵向扫描时，从前往后遍历所有字符串的每一列，比较相同列上的字符是否相同，如果相同则继续对下一列进行比较，如果不相同则当前列不再属于公共前缀，当前列之前的部分为最长公共前缀。z

    • 时间复杂度： O(mn)，其中 m是字符串数组中的字符串的平均长度，n是字符串的数量。最坏情况下，字符串数组中的每个字符串的每个字符都会被比较一次
    • 空间复杂度： O(1)。使用的额外空间复杂度为常数

  3. 分治

    分支算法中的将大问题拆分子问题，由子问题的结果最终得出大问题的结果

    在这里：

    • 多个字符串的公共串分解为，两两 得公共串，
    • 新的公共串列 又分解为，两两得公共串
    • 类似于对横向扫描的优化，横向的循环对比，这里可以快速对比（类似排序算法中归并排序，还可以多路归并）
    • 时间复杂度：O(mn)，其中 m 是字符串数组中的字符串的平均长度，nn 是字符串的数量。
    • 空间复杂度：O(mlogn)，其中 m 是字符串数组中的字符串的平均长度，nn 是字符串的数量。空间复杂度主要取决于递归调用的层数，层数最大为 log n，每层需要 m 的空间存储返回结果# Day9 最长公共前缀

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

https://leetcode-cn.com/problems/longest-common-prefix/

示例1：

输入：strs = ["flower","flow","flight"]
输出："fl"

示例2：

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

提示：

0 <= strs.length <= 200
0 <= strs[i].length <= 200
strs[i] 仅由小写英文字母组成

Java解法

思路：

  • 简单思路：两两取出公共串，做为新串与下个字符串比较，有公共继续知道比较完成，输出；若无则表示没有公共串

  • 犯二：这里做拆分求两个字符串的公共前缀做成了求公共子串

    public static String getCommon(String s1, String s2) {
        int i = 0;
        List<Character> list = new ArrayList<>();
        String result = "";
        while (i<s1.length()&&i<s2.length()){
            if (s1.charAt(i)==s2.charAt(i)) {
                list.add(s1.charAt(i));
            }else {
                String temp = "";
                for (Character character : list) {
                    temp+=character;
                }
                list.clear();
                result = result.length()>=temp.length()?result:temp;
            }
            i++;
        }
        String temp = "";
        for (Character character : list) {
            temp+=character;
        }
        result = result.length()>=temp.length()?result:temp;
        return result;
    }

package sj.shimmer.algorithm;

/**
 * Created by SJ on 2021/2/2.
 */

class D9 {
    public static void main(String[] args) {
        System.out.println(longestCommonPrefix(new String[]{"flower","flow","flight"}));
        System.out.println(longestCommonPrefix(new String[]{"dog","racecar","car"}));
        System.out.println(longestCommonPrefix(new String[]{"cir","car"}));
        System.out.println(longestCommonPrefix(new String[]{"flower","fkow"}));
    }
    public static String longestCommonPrefix(String[] strs) {
        if (strs==null||strs.length==0) {
            return "";
        }
        String result = strs[0];
        for (int i = 1; i < strs.length; i++) {
            String common = getCommonPre(result, strs[i]);
            if (common!=null&&common!="") {
                result = common;
            }else {
                return "";
            }
        }
        return result;
    }

    public static String getCommonPre(String s1, String s2) {
        int i = 0;
        String result = "";
        while (i<s1.length()&&i<s2.length()){
            if (s1.charAt(i)==s2.charAt(i)) {
                result+=s1.charAt(i);
            }else {
                return result;
            }
            i++;
        }
        return result;
    }
}

官方解

  1. 横向扫描

    上方同样的思路,但官方的求公共前缀方法明显更好，计算位置再剪切，提高了大量效率

    public  String getCommonPre(String str1, String str2) {
>        int length = Math.min(str1.length(), str2.length());
>         int index = 0;
>         while (index < length && str1.charAt(index) == str2.charAt(index)) {
>             index++;
>         }
>         return str1.substring(0, index);
>     }
> ```
>
> ![](http://sj_tick.gitee.io/sjarticle-image/img/LeetCode//D9-1.png)
    • 时间复杂度： O(mn)，其中 m是字符串数组中的字符串的平均长度，n是字符串的数量。最坏情况下，字符串数组中的每个字符串的每个字符都会被比较一次
    • 空间复杂度： O(1)。使用的额外空间复杂度为常数

  2. 纵向扫描

    纵向扫描时，从前往后遍历所有字符串的每一列，比较相同列上的字符是否相同，如果相同则继续对下一列进行比较，如果不相同则当前列不再属于公共前缀，当前列之前的部分为最长公共前缀。z

    • 时间复杂度： O(mn)，其中 m是字符串数组中的字符串的平均长度，n是字符串的数量。最坏情况下，字符串数组中的每个字符串的每个字符都会被比较一次
    • 空间复杂度： O(1)。使用的额外空间复杂度为常数

  3. 分治

    分支算法中的将大问题拆分子问题，由子问题的结果最终得出大问题的结果

    在这里：

    • 多个字符串的公共串分解为，两两 得公共串，
    • 新的公共串列 又分解为，两两得公共串
    • 类似于对横向扫描的优化，横向的循环对比，这里可以快速对比（类似排序算法中归并排序，还可以多路归并）
    • 时间复杂度：O(mn)，其中 m 是字符串数组中的字符串的平均长度，nn 是字符串的数量。
    • 空间复杂度：O(mlogn)，其中 m 是字符串数组中的字符串的平均长度，nn 是字符串的数量。空间复杂度主要取决于递归调用的层数，层数最大为 log n，每层需要 m 的空间存储返回结果
©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成，浏览时请结合常识与多方信息审慎甄别。
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

相关阅读更多精彩内容

  • 最长公共前缀
    参考：https://leetcode-cn.com/problems/two-sum/solution/zui-...
    iamlyly阅读 4,059评论 0赞 0
  • 最长公共前缀
    一、问题 编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀，返回空字符串。 示例 1：输入：["f...
    Djbfifjd阅读 3,427评论 0赞 2
  • <leetcode - 14> 最长公共前缀
    题目描述 编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀，返回空字符串 ""。 示例 1:输入:...
    hbhey阅读 1,391评论 0赞 0
  • 2020-10-14 最长公共前缀
    题目描述 编写一个函数来查找字符串数组中的最长公共前缀,如果不存在公共前缀，返回空字符串"" 题目分析 数组元素 ...
    如沐春风ei阅读 2,144评论 0赞 0
  • leetcode14 最长公共前缀
    自己的解法 自己的解法就是先找出长度最短的字符串，然后以这个字符串为基准，去遍历其它字符串，看大家的前几位是否是相...
    justonemoretry阅读 984评论 0赞 0

友情链接更多精彩内容