14. Longest Common Prefix

LeetCode
,

My Solution (Vertical Scanning)

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
class Solution {
    public String longestCommonPrefix(String[] strs) {
        StringBuilder sb = new StringBuilder();
        // get min length
        int min_len = Integer.MAX_VALUE;
        for (int i = 0; i < strs.length; i++){
            if (strs[i].length() < min_len){
                min_len = strs[i].length();
            }
        }

        if (min_len == 0){
            return sb.toString();
        }

        // check char
        for (int i = 0; i < min_len; i++){
            char last = strs[0].charAt(i);
            boolean same = true;
            for (int j = 1; j < strs.length; j++){
                if (strs[j].charAt(i) != last){
                    return sb.toString();
                }
            }
            if (same){
                sb.append(last);
            }
        }
        return sb.toString();

    }

}

Remarks:

  1. This is Vertical Scanning, by comparing the same position of all strings.

Horizontal Scanning

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0) return "";

        String prefix = strs[0];

        for (int i = 1; i < strs.length; i++) {
            //cut the prefix if does not match
            while (!strs[i].startsWith(prefix)) {
                prefix = prefix.substring(0, prefix.length() - 1);
                if (prefix.isEmpty()) return "";
            }
        }

        return prefix;
    }
}