萤火小屋

优律的知识库

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

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

力扣14题-最长公共前缀

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

题目描述

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

样例

示例 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题-三数之和
  • 文章目录
  • 站点概览
优律

优律

优律的知识库

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