首页 > 其他分享 >最长公共前缀

最长公共前缀

时间:2024-10-31 11:20:40浏览次数:1  
标签:前缀 strs 公共 字符串 com 最长

最长公共前缀

题目链接:牛客
描述
给你一个大小为 n 的字符串数组 strs ,其中包含n个字符串 , 编写一个函数来查找字符串数组中的最长公共前缀,返回这个公共前缀。

示例

输入:["abca","abc","abca","abc","abcc"]
返回值:"abc"

思路

step1: 确定第i个与第i+1个字符串子串相同的公共前缀com。
step2: 将上面找到的前缀com与第i+2个子串进行对比,更新com
step3: 重复上述步骤,最终得到字符串的最长公共前缀

实现代码

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     * @param strs string字符串一维数组 
     * @return string字符串
     */
    public String longestCommonPrefix (String[] strs) {
        int len = strs.length;
        if(len==0)  return "" ;
        if(len==1)  return strs[0];
        String com = prefix(strs[0],strs[1]);
        for(int i = 2; i<len; i++){
            com = prefix(com, strs[i]);
        }
        return com;
    }
    //返回两子串公共前缀函数
    public  String prefix(String s1, String s2){
        String com = "";
        for(int i=0; i<s1.length() && i<s2.length(); i++){
            if(s1.charAt(i) == s2.charAt(i)){
                com = com + s1.charAt(i);
            }else{
                return com;
            }
        }
        return com;
    }
}

标签:前缀,strs,公共,字符串,com,最长
From: https://www.cnblogs.com/dwhere/p/18517349

相关文章

  • 二维前缀和模板
    二维前缀和模板题目描述:输入一个n行m列的整数矩阵,再输入q个询问,每个询问包含四个整数x1,y1,x2,y2,表示一个子矩阵的左上角坐标和右下角坐标。对于每个询问输出子矩阵中所有数的和。输入格式:第一行包含三个整数n,m,q接下来n行,每行包含m个整数,表示整数矩阵。接下来......
  • 【算法】前缀树
    基本内容以树的方式存储字符串的数据结构,方便字符串的查找及判断是否为某一字符串的前缀入门例子PHONELST-PhoneList-洛谷|计算机科学教育新生态题目要求:判断一组字符串中是否存在某一字符串是另一字符串的前缀。例如在{“911”,“91140”,“20”,“912”}中,“911”......
  • (算法)最⻓公共⼦序列————<动态规划>
    1.题⽬链接:1143.最⻓公共⼦序列2.题⽬描述:3.解法(动态规划):算法思路:1.状态表⽰:对于两个数组的动态规划,我们的定义状态表⽰的经验就是:        i.选取第⼀个数组[0,i]区间以及第⼆个数组[0,j]区间作为研究对象;        ii.结合题⽬要求,定义状态......
  • 3. 无重复字符的最长子串(中)
    目录题目题解:滑动窗口题目给定一个字符串s,请你找出其中不含有重复字符的最长子串的长度。示例1:输入:s="abcabcbb"输出:3解释:因为无重复字符的最长子串是"abc",所以其长度为3示例2:输入:s="pwwkew"输出:3解释:因为无重复字符的最长子串是"wke",所以......
  • 第四届公共艺术与人文发展国际学术会议 (ICPAHD 2024)
     第四届公共艺术与人文发展国际学术会议 (ICPAHD2024)将于2024年12月27-29日在中国成都举行。ICPAHD2024将围绕“公共艺术与人文发展”的最新研究领域,为来自国内外高等院校、科学研究所、企事业单位的专家、教授、学者、工程师等提供一个分享专业经验,扩大专业网络,面对面交......
  • 算法笔记:Day-04(二维前缀和)
    二维数组及滚动数组304.二维区域和检索-矩阵不可变classNumMatrix{privatefinalint[][]sum;publicNumMatrix(int[][]matrix){intm=matrix.length;intn=matrix[0].length;sum=newint[m+1][n+1];for(in......
  • 2024-10-26:最长公共后缀查询。用go语言,给定两个字符串数组 wordsContainer 和 wordsQu
    2024-10-26:最长公共后缀查询。用go语言,给定两个字符串数组wordsContainer和wordsQuery,要对每个wordsQuery[i]找到一个与其有最长公共后缀的字符串。如果有多个字符串与wordsQuery[i]有相同的最长公共后缀,则返回在wordsContainer中最早出现的那个。最后,返回一个整数数组a......
  • 最长回文长度
     小伙伴们大家好,今天给大家带来一道算法题:如何找一个字符串中的最大回文长度。何为回文?简单来讲就是正着读和倒着读结果相同,如aba。暴力算法 给定一个字符串s=“abac”,经典的暴力算法思想是对每个字符进行回文串扩充。i=0,对a进行扩充,发现其左边没有元素,因此回文长度为0。......
  • 公共云和私有云在云计算中有什么区别
    PublicCloud和PrivateCloud在云计算中的区别:1.申请主体不同;2.服务范围不同;3.安全性机制不同;4.定制选项不同;5.费用结构不同。PublicCloud和PrivateCloud是云计算中两种主要的部署模型,它们在服务范围、安全性、定制性、成本等方面存在显著差异。1.申请主体不同PublicCloud......
  • 20241023 模拟赛(GCD,包含,前缀,移动)
    看题戳这里总结20min自习。上来30min先把t1写了。然后t2没看明白,先打了个暴力?然后发现值域很离谱,dfs就行了。t3t4看了一眼就跑路了。解析A.GCD难度:黄注意到只有当\(n=\)素数\(p\)的正整数次幂时,有\(f(n)=p\),其他情况都是\(f(n)=1\)。所以用欧拉筛筛一遍......