leetcode 最长公共前缀 （Java）_leetcode 最长公共前缀 java

题目如下

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

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

示例一：
输入：strs = ["flower","flow","flight"]
输出："fl"

示例二：
输入：strs = ["dog","racecar","car"]
输出：""
解释：输入不存在公共前缀。
1
2
3
4
5
6
7
8
9
10
11
12

题目链接

第一种解法：

• 横向扫描
• 先判断第一个字符和第二个字符的最长前缀，
• 然后判断第二个和第三个字符的最长前缀，以此类推
• 如图
  

class Solution {
    public String longestCommonPrefix(String[] strs) {
        // 判断第一个字符串和第二个字符串有几个是相同的，
        //      判断第二个字符串和第三个有几个是相同的，依次进行，不断进行更新

        int count = strs.length;

        if (strs == null || count == 0)
            return "";

        // 先把第一个字符串作为最长前缀
        String prefix = strs[0];

        
        for(int i=1; i < count; i++) {
            prefix = longestCommonPrefix(prefix, strs[i]);
            // 只要为空，则说明后一个字符串和前一个字符串不同，此时返回空串；
            if(prefix.length() == 0)
                break; 
        }
        
        return prefix;
    }

    private String longestCommonPrefix(String str1, String str2) {
        // 比较两个字符串中的长度较小值
        int minCount = Math.min(str1.length(), str2.length());
        int index = 0;
        
        while(index < minCount && 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

第二种解法：

• 纵向扫描
• 把每个字符串第一个进行比较，第二个字符串进行比较
• 如图
  

class Solution {
    public String longestCommonPrefix(String[] strs) {
        // 判断所有字符串中的第一个字符，第二个字符，第n个字符是否相等
        if (strs == null || strs.length == 0)
            return "";

          int count = strs.length;
        for(int i = 0; i < strs[0].length(); i++) {
            char c = strs[0].charAt(i);

            for(int j = 1; j < count; j++) {
                // 如果某一列中的字符不等，则返回；或者是，长度等于该字符串的长度，则说明该字符已经遍历完了
               if (i == strs[j].length() || strs[j].charAt(i) != c) {
                    return strs[0].substring(0, i);
                }
            }
        }
        
        // 上面没进行返回的话，则说明第一个字符串就是最长公共前缀
        return strs[0];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

第三种方法：

• 分治法
• 假设有四个字符串，把第一个和第二个共同的字符串找出来，把三四个共同的字符串找出来
• 然后把这两个共同的字符串再拿出来进行比较
• 如图
  

class Solution {
    public String longestCommonPrefix(String[] strs) {
        // 分治法：假设有四个字符串，把第一个和第二个共同的字符串找出来，把三四个共同的字符串找出来
        //      然后把这两个共同的字符串再拿出来进行比较

        if (strs == null || strs.length == 0)
            return "";
        else
            return longestCommonPrefix(strs, 0, strs.length - 1);
    }

    private String longestCommonPrefix(String[] strs, int start, int end) {
        // 如果相等，则返回较小的那个字符串，即第一个字符串
        if (start == end) {
            return strs[start];
        } else {
            int mid = (end - start) / 2 + start;
            
            // 递归进行查找
            String lcpLeft = longestCommonPrefix(strs, start, mid);
            String lcpRight = longestCommonPrefix(strs, mid + 1, end);
            
            // 找到两个字符串共有的部分
            return commonPrefix(lcpLeft, lcpRight);
        }
    }

    private String commonPrefix(String lcpLeft, String lcpRight) {
        int minCount = Math.min(lcpLeft.length(), lcpRight.length());
        for(int i = 0; i < minCount; i++)
            if(lcpLeft.charAt(i) != lcpRight.charAt(i))
            	// 找到共同的部分
                return lcpLeft.substring(0,i);

		// 则说明该字符共有的部分是最小长度的那一部分
        return lcpLeft.substring(0,minCount);
    }
}
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

第四种方法：

• 二分法
• 看不太懂
• 如图
  

class Solution {
    public String longestCommonPrefix(String[] strs) {
        // 二分法：把最小的字符串进行二分，把该字符串的左边的与后面的进行匹配
        //      然后把该字符串右边的进行匹配
        // 为什么是最小的字符串，因为最长前缀，肯定是最小的那个字符串的,比如leetcode,let,letc 最小的肯定是let

        if (strs == null || strs.length == 0)
            return "";
        
        int minLength =  strs[0].length();
        for(String str : strs) {
            // 找到该字符数组中的最小字符串的长度
            minLength = Math.min(minLength,str.length());
        }

        int left = 0;
        int right = minLength;

        while(left < right) {
            int mid = (right - left + 1) / 2 + left;
            if(isCommonPrefix(strs,mid)) {

                left = mid;
            } else {
                right = mid - 1;
            }
        }
        return strs[0].substring(0,left);
    }

    private boolean isCommonPrefix(String strs[], int length) {
        String strs0 = strs[0].substring(0,length);

        int count = strs.length;

        for(int i = 1; i < count; i++) {
            String str = strs[i];
            for(int j=0; j < length; j++) {
                if(strs0.charAt(j) != str.charAt(j)) {
                    return false;
                }
            }
        }

        return true;
    }
}

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