LeetCode之最长公共前缀（Java实现）_flow flight java

一、题目描述

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

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

示例1：

输入: ["flower","flow","flight"]
输出: "fl"
1
2

示例2：

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

说明:

所有输入只包含小写字母 a-z 。

二、题目分析

看到题目后，首先要想到字符数组为空的情况，这时无需判断，直接返回" “就好。
还有一种情况也可以直接返回” "，当strs.length()==0时，也不用判断。

接着说下我们的大体思路：定义一个函数，传入字符数组的前两个字符串，使他返回两个字符串的公共部分（从索引值为0处开始），接着建立循环，将该串与字符数组的下一个字符串，进行共有部分判断（借助于刚定义的函数），如果返回出来的串的长度不为0，则直接将本串作为最终结果返回；如果该字符串长度为0，说明没有共有部分，返回" "。

三、代码实现

定义一个返回共有部分的函数。
代码实现：

 //定义函数，用来返回两个字符串中相同的部分
    public static String AAA(String str1,String str2){
        //代表索引值
        int index = 0;
        //取两个字符串中长度较小的那个当做循环条件，因为是按字符匹配，所有循环次数不能超过长度较小的子串的长度
        int min = Math.min(str1.length(), str2.length());
        //索引值合法时，并且两个串中相同索引的字符也相同，则移动索引值到下一个位置
        while(index<min && str1.charAt(index)==str2.charAt(index)){
            index++;
        }
        //返回两个字符串中相同的部分
        return str1.substring(0,index);
    }

1
2
3
4
5
6
7
8
9
10
11
12
13
14

具体算法思想，单独定义一个变量存储字符数组首元素，将他和字符数组下一个元素作为参数，传入自己定义的函数并获得共有部分，将共有部分和数组下一个值继续当参数传入函数，看是否能继续找到共有部分，找不到则返回空。
代码实现:

public static String longestCommonPrefix(String[] strs) {

        //如果字符数组为空，或者长度为0。直接返回空
        if(strs ==null||strs.length==0){
            return "";
        }
        //记录数组长度
        int length = strs.length;
        //定义sign存储第一个元素
        String sign = strs[0];

        for (int i = 0; i < length; i++) {
            //每次都用两个字符串中相同的部分去跟下一个字符串进行比较，并将他们的相同部分或取出来，在进行比较，知道循环结束
            sign = AAA(sign, strs[i]);
            //如果相同部分的字符串长度为0，说明没有公共部分，直接跳出循环
            if(sign.length()==0){
                break;
            }
        }
        return sign;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

四、完整代码

package Demo06;/*
 *@Author：
 *@Date:2020/11/3 14:10
 */

public class Test04 {
    public static void main(String[] args) {
        String[] s = {"cir","car"};
//        String[] s = {};
        String s1 = longestCommonPrefix(s);
        System.out.println(s1);
    }
    public static String longestCommonPrefix(String[] strs) {

        //如果字符数组为空，或者长度为0。直接返回空
        if(strs ==null||strs.length==0){
            return "";
        }
        //记录数组长度
        int length = strs.length;
        //定义sign存储第一个元素
        String sign = strs[0];

        for (int i = 0; i < length; i++) {
            //每次都用两个字符串中相同的部分去跟下一个字符串进行比较，并将他们的相同部分或取出来，在进行比较，知道循环结束
            sign = AAA(sign, strs[i]);
            //如果相同部分的字符串长度为0，说明没有公共部分，直接跳出循环
            if(sign.length()==0){
                break;
            }
        }
        return sign;
    }
        //定义函数，用来返回两个字符串中相同的部分
    public static String AAA(String str1,String str2){
        //代表索引值
        int index = 0;
        //取两个字符串中长度较小的那个当做循环条件，因为是按字符匹配，所有循环次数不能超过长度较小的子串的长度
        int min = Math.min(str1.length(), str2.length());
        //索引值合法时，并且两个串中相同索引的字符也相同，则移动索引值到下一个位置
        while(index<min && str1.charAt(index)==str2.charAt(index)){
            index++;
        }
        //返回两个字符串中相同的部分
        return str1.substring(0,index);
    }

}

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
40
41
42
43
44
45
46
47
48
49