萤火小屋

优律的知识库

  • 首页
  • 归档
  • 分类
  • 标签
  • 留言
  • 关于

  • 搜索
双指针 力扣 动态代理 Git YAML SpringBoot SpringMVC 回溯算法 分治算法 归并排序 快排 手撕 事务 MySQL索引 MySQL 小技巧 Spring Framework Spring 动态规划 Linux Android 贪心算法 操作系统 进程调度模拟 IPv6 数据库 计算机组成原理 计算机基础 栈 Java 静态路由 路由器 交换机 数字通信 网络工程 计算机网络 Web http 大学学习技巧 程序设计 算法

力扣14题-最长公共前缀

发表于 2022-03-29 | 分类于 力扣刷题 | 0 | 阅读次数 25

题目描述

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

样例

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

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

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

题目评估

知识点:字符串
官方难度:简单

分析

从第一个字符串的第一个字符,采用“龙摆尾”式串串得方式比较每个字符串的纵向字符是否一致。

Java代码题解

class Solution {
    public String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0) {
            return "";
        }
        String first = strs[0];
        // 遍历第一个字符串的每个字符
        for (int i = 0; i < first.length(); i++) {
            char c = first.charAt(i);
            // 遍历每个字符串比较第i位与第一个字符串的第i位字符
            for (int j = 1; j < strs.length; j++) {
                // 第j个字符串越界或者第一个字符串的第i位不等于当前字符串的第i位字符返回
                if (i == strs[j].length() || c != strs[j].charAt(i)) {
                    return first.substring(0, i);
                }
            }
        }
        // 否则返回第一个字符串,第一个字符串就是最长公共串
        return first;
    }
}

复杂度分析

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

# 算法 # 程序设计 # 力扣
力扣13题-罗马数字转整数
力扣第15题-三数之和
  • 文章目录
  • 站点概览
优律

优律

优律的知识库

67 日志
17 分类
41 标签
E-mail Twitter Instagram
Links
  • CZLisyx - 浮生志
  • Vedfolnir
0%
© 2019 — 2022 萤火小屋——优律的博客网站
网站已勉强运行 
Halo博客系统技术支持