Leetcode --- NO.14 最长公共前缀（Java）_java前缀树求解leetcode14

题目描述

class Solution {
    public String longestCommonPrefix(String[] strs) {

    }
}
1
2
3
4
5

题目分析

• 根据题目可知：给定一个字符串数组，找出数组内所有字符串的公共前缀
• 什么叫前缀？即从第一个字符开始就要相等，如果都没有，则返回空字符串

解法分析

• 解法一：横向比较，遍历字符串，然后两两比较获得公共部分，再用公共部分去与下一个字符串对比，直到最后，纵向比较就是按照字符进行比较，先比较每一个字符串的第一个字符，再比较第二个，一次类推，直到出现不一样的，就返回。
• 解法二：先将字符串按字典顺序排序，排序后只需要对比第一个和最后一个字符串的公共前缀即可。
• 解法三：采用分治法，二分法等，降低遍历字符串的复杂度

上代码

• 解法一： 用时击败32%，内存消耗击败5%，可见有多费时费力

class Solution {
    public String longestCommonPrefix(String[] strs) {
        int n = strs.length;
        if (n == 0) return "";
        String res = strs[0];
        for (int i = 1; i < strs.length; i++) {
            StringBuilder sb = new StringBuilder();
            int len = Math.min( strs[i].length(), res.length() );
            for (int j = 0; j < len; j++) {
                if ( res.charAt(j) == strs[i].charAt(j) ){
                    sb.append(res.charAt(j));
                } else {
                    break;
                }
            }
            res = sb.toString();
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

• 偶然看到了一段代码，很巧妙，使用了indexOf()函数：查找指定字符或字符串在字符串中第一次出现地方的索引，未找到的情况返回 -1.

class Solution {
	public String longestCommonPrefix(String[] strs) {
		if (strs.length == 0) 
			return "";
		String prefix = strs[0];
		for (int i = 1; i < strs.length; i++){
	  		while (strs[i].indexOf(prefix) != 0) {
	  			// 等于0就代表从第0个字符开始就已经出现了指定的字符串
	  			// 因为是公共前缀，所以如果有公共部分，则索引一定为0
	  			// 不等于0，就说明没有从头就找到对应的子串，
	  			// 于是使用substring函数，将prefix串减掉最后一个字符
	      		prefix = prefix.substring(0, prefix.length() - 1);
	      		if (prefix.isEmpty()) return "";
	  		}  
		}      
		return prefix;
	}
}
作者：LeetCode
链接：https://leetcode-cn.com/problems/longest-common-prefix/solution/zui-chang-gong-gong-qian-zhui-by-leetcode/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

• 解法二：先对字符串数组进行字典排序，然后直接判断第一个和最后一个的公共前缀即可
  用时击败82%，内存消耗击败37%

class Solution {
    public String longestCommonPrefix(String[] strs) {
        int n = strs.length;
        if (n == 0) return "";
        Arrays.sort(strs);
        String first = strs[0];
        String last = strs[n-1];
        StringBuilder sb = new StringBuilder();
        int len = Math.min( first.length(), last.length() );
        for (int j = 0; j < len; j++) {
            if ( first.charAt(j) == last.charAt(j) ){
                sb.append(first.charAt(j));
            } else {
                break;
            }
        }
        return sb.toString();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19