Java解决最长公共前缀

Java解决最长公共前缀

01 题目

• 编写一个函数来查找字符串数组中的最长公共前缀。

  如果不存在公共前缀，返回空字符串 ""。

  示例 1：

  输入：strs = ["flower","flow","flight"]
  输出："fl"
  1
  2

  示例 2：

  输入：strs = ["dog","racecar","car"]
  输出：""
  解释：输入不存在公共前缀。
  1
  2
  3

  提示：

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

02 知识点

• 字符串函数
• 双重循环

03 我的题解思路

public class longestCommonPrefix {
	public static void main(String[] args) {
//		测试数据
		String[] strs= {"dog","racecar","car"};
		System.out.println(longestCommonPrefix(strs));
	}
	public static String longestCommonPrefix(String[] strs) {
//		获取数组首个元素
		String s=strs[0];
//		特殊情况，数组长度为1直接返回
		if(strs.length==1){
			return s;
		}
//		外置死循环，内部条件脱离循环
		while(true){
//			遍历数组
			for (int i = 1; i < strs.length; i++) {
//				判断当前字符串的前缀是否为公共前缀
				if(!strs[i].startsWith(s)) {
//					不是则公共前缀递减并结束本次循环
					s=s.substring(0,s.length()-1);
					break;
				}
//				判断当前数组长度，为最后一个元素则返回公共前缀
				if(i==strs.length-1) {
					return s;
				}
			}
//			当公共前缀递减为空则返回空
			if(s=="") {
				return "";
			}
			
		}
		
    }

}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39