LeetCode每日一题之最长公共子串_最长公共子串 leetcode

LeetCode每日一题之最长公共子串

编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 “”。

实例：
输入：strs = [“flower”,“flow”,“flight”]
输出：“fl”

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

思路

1、这道题首先应该将字符数组中的每个元素读取出来，从而实现他们直接的比对(这一点不管是方法一，还是方法二，都是共通的)
2、其次，读取出来后，就是比对，从而得到共同的最长前缀(方法一和方法二在这里就出现了分化：
方法一：
采取重写一个方法，实现比对两个字符串的匹配情况，返回最长公共子串，然后比较所有字符串
方法二：
调用startsWith()方法，先比对所有字符串是否符合，不符合则将字符串裁断-1，再比对，再剪短，得到最长公共子串)
3、最后就是返回该值了

方法一：

class LongCommonStr{
    public String LongCommonStr(String[] str){
        if(str==null||str.length==0){
            return "";
        }
//总结：对于任何传入方法中的数组类型，第一步都是判断一下它是否为空数组，一般这样操作，直接就能得到一种情况的解
        String s=str[0];
        //设置索引，方便遍历
        for(int i=0;i<str.length;i++){
            s=LongCommonStr(s,str[i]);
            //更新所能获得的最大公共子串
            if(s.length()==0){
                break;
//对于一个循环，一般我们都要考虑两种情况，一种是正常结束了循环，一种是触发条件，然后结束循环
            }
        }
    return s;
    }
    public String LongCommonStr(String str1,String str2){
        int length=Math.min(str1.length(),str2.length());
        //Math是内置包，不需要导包
        int index=0;
        while(index<length&&str1.charAt(index)==str2.charAt(index)){
            //通过charAt()方法获取字符串中的每一位
            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

方法二：

public class LongCommonStr1 {
    public String LongCommonStr1(String[] str){
        if(str==null||str.length==0){
            return "";
        }
        String s=str[0];
        for(int i=0;i<str.length;i++){
            //或者用另外一种循环    for (String string : str)
            while(!str[i].startsWith(s)) {
            //换了之后这里也对应换一下   while(!string.startsWith(s))
                if (s.length() == 0) {
                    break;
                }
                s=s.substring(0,s.length()-1);
            }
        }
        return s;
        //这个方法的好处在于直接用startsWith()
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

结尾处的几点思考

1、对于任何传入方法中的数组类型，第一步都是判断一下它是否为空数组，因为一般这样操作，直接就能得到一种情况的解

2、温故：
实现for遍历循环的方法除了
正常for(int i=0;i<str.length;i++)
还有for(String string :str)

3、对于一个循环，一般我们都要考虑两种情况，一种是正常结束了循环，一种是触发条件，然后结束循环（模板了，直接用）

4、对于java，有很多内置方法来解决问题，如之前的reverse()方法，今天的startsWith()方法，以及常用的charAt(); 多查查，多练练