前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >14、最长公共前缀(Java)

14、最长公共前缀(Java)

作者头像
魚迹
发布2023-05-06 21:27:09
2380
发布2023-05-06 21:27:09
举报

LeetCode-14、最长公共前缀

1、题目描述

题目描述: 编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀,返回空字符串 “”。

示例1: 输入:strs = [“flower”,“flow”,“flight”] 输出:“fl”

示例2: 输入:strs = [“dog”,“racecar”,“car”] 输出:“” 解释:输入不存在公共前缀。

2、解题思路

解题思路: 对于空字符数组直接返回“”作为公共前缀;对于非空数组,则随机选一个字符串作为初始公共前缀(因为公共前缀的最大长度一定小于等于数组中最短的那个字符串,所以可以随机选择一个字符串作为初始前缀),之后使用String类中的方法startsWith()在for循环中判断字符串是否含有该前缀,若没有则缩短公共前缀的长度,在缩短之前判断变量(公共前缀)的长度是否为0,若为0则返回空字符串“”。

解题步骤如下: 1、判断字符数组的长度是否为0,若为0则返回空字符串“” 2、对于非空字符串则选择第一个字符串作为初始公共前缀 3、遍历字符串数组,判断前缀变量的长度是否为0,若不为0则使用startswith方法判断是否含有该公共前缀 4、若不该前缀,则缩短前缀变量的长度,继续判断 5、当遍历结束后,返回公共前缀。

3、代码实现

代码语言:javascript
复制
class Solution {
    public String longestCommonPrefix(String[] strs) {
        if(strs.length == 0 )     //空则返回“”
            return "";
        String s = strs[0];       //初始前缀
        for(String str :strs)
        {
            while(!str.startsWith(s))   //判断是否含有该前缀
            {
                if(s.length()==0)
                    return "";
                s = s.substring(0,s.length()-1);//前缀长度-1
            }
        }
            return s;
    }
}

4、解题记录

在解决该题时,最初的思路是先遍历字符串数组,找出字符串长度最短的字符串作为初始前缀的值,然后进行横向扫描解题。后通过借鉴他人思路,使用startsWith方法进行前缀判断。 后查看官方题解,看到多种解题思路,如二分查找、纵向扫描等方法。

在这里插入图片描述
在这里插入图片描述
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2022-12-30,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • LeetCode-14、最长公共前缀
  • 1、题目描述
  • 2、解题思路
  • 3、代码实现
  • 4、解题记录
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档