赞
踩
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀,返回空字符串 ""
。
示例 1:
- 输入:strs = ["flower","flow","flight"]
- 输出:"fl"
示例 2:
- 输入:strs = ["dog","racecar","car"]
- 输出:""
- 解释:输入不存在公共前缀。
提示:
1 <= strs.length <= 200
0 <= strs[i].length <= 200
strs[i]
仅由小写英文字母组成
Hint:带测试版
- /**
- * @description:
- * @author: r1ng
- * @time: 2023/7/31 22:07
- */
- public class LongestCommonPrefix {
- public static String longesCommonPrefix(String[] strs) {
- //如果输入的strs为空,则返回空字符串""
- if(strs.length==0){
- return "";
- }
- //定义一个ans为strs.[0],获取到strs的第一个字符串为了一下面的循环比较
- String ans = strs[0];
- for(int i=0; i<strs.length; i++){
- //在这里定义j=0,而不是在for里面定义;是为了ans.substring(0,j)能调用j的值
- int j = 0;
- for(;j<ans.length() && j<strs[i].length(); j++){
- //比较俩个字符串相同的部分,不相同则退出循环
- if(ans.charAt(j) != strs[i].charAt(j))
- break;
- }
- //获取从0到j相同的字符串
- ans = ans.substring(0,j);
- //如果ans获取的结果为空则返回空字符
- if(ans.equals(" "))
- return ans;
- }
- //返回最终获取到的ans
- return ans;
- }
-
- public static void main(String[] args) {
- String [] strs = {"flower","flow","flight"};
- String s = longesCommonPrefix(strs);
- System.out.println(s);
-
- }
- }

Hint:不带测试版本
- class Solution {
- public String longestCommonPrefix(String[] strs) {
- //如果输入的strs为空,则返回空字符串""
- if(strs.length==0){
- return "";
- }
- //定义一个ans为strs.[0],获取到strs的第一个字符串为了一下面的循环比较
- String ans = strs[0];
- for(int i=0; i<strs.length; i++){
- //在这里定义j=0,而不是在for里面定义;是为了ans.substring(0,j)能调用j的值
- int j = 0;
- for(;j<ans.length() && j<strs[i].length(); j++){
- //比较俩个字符串相同的部分,不相同则退出循环
- if(ans.charAt(j) != strs[i].charAt(j))
- break;
- }
- //获取从0到j相同的字符串
- ans = ans.substring(0,j);
- //如果ans获取的结果为空则返回空字符
- if(ans.equals(" "))
- return ans;
- }
- //返回最终获取到的ans
- return ans;
- }
- }

当字符串数组长度为 0 时则公共前缀为空,直接返回;
令最长公共前缀 ans 的值为第一个字符串,进行初始化;
遍历后面的字符串,依次将其与 ans 进行比较,两两找出公共前缀,最终结果即为最长公共前缀;
如果查找过程中出现了 ans 为空的情况,则公共前缀不存在直接返回;
时间复杂度:O(s)O(s)O(s),s 为所有字符串的长度之和。
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。