一、题目描述
来源:力扣(LeetCode)
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀,返回空字符串 ""。
示例 1:
输入:strs = ["flower","flow","flight"]
输出:"fl"
示例 2:
输入:strs = ["dog","racecar","car"]
输出:""
解释:输入不存在公共前缀。
提示:
- 1 <= strs.length <= 200
- 0 <= strs[i].length <= 200
- strs[i] 仅由小写英文字母组成
二、思路分析
- 当字符串数组长度为 0 时则公共前缀为空,直接返回
- 将最长公共前缀 resStr 初始化为 数组中第一个字符串
- 遍历后面的字符串,依次将其与 resStr 进行比较,找出两个字符串公共前缀,并更新resStr
- 最终的 resStr 即为我们要的最长公共前缀
- 如果遍历过程中 resStr 为 null 了,则代表不可能存在最长公共前缀了,直接返回
三、代码实现
class Solution { public String longestCommonPrefix(String[] strs) { if (strs.length ==0) return ""; String resStr = strs[0]; for (int i =0 ; i < strs.length;i++){ int j =0; for (; j <resStr.length() && j < strs[i].length();j++){ if (resStr.charAt(j) != strs[i].charAt(j)){ break; } } resStr = resStr.substring(0,j); } return resStr; } }
复杂度分析
时间复杂度:
网络异常,图片无法展示
|
m
是字符串数组中的字符串的平均长度,
n
是字符串的数量。最坏情况下,字符串数组中的每个字符串的每个字符都会被比较一次
空间复杂度:
网络异常,图片无法展示
|
运行结果
网络异常,图片无法展示
|
总结
这道题目比较简单,就是一个模拟遍历的题目。继续加油~