[LeetCode] 14. Longest Common Prefix

Posted on | In

Problem

Write a function to find the longest common prefix string amongst an array of strings.

If there is no common prefix, return an empty string "".

Example 1:

1
2
Input: ["flower","flow","flight"]
Output: "fl"

Example 2:

1
2
3
Input: ["dog","racecar","car"]
Output: ""
Explanation: There is no common prefix among the input strings.

Note:

All given inputs are in lowercase letters a-z.

Explanation

  1. We can use the first string in the array as a compare string.

  2. Loop through the first string’s character, and loop from the second string to last string, compare the corresponding index character. If all matches, we append that character to a result stringbuilder, and loop from the second character of the first string and repeat. If not match or finish looping, we return the stringbuilder.

  3. Another approach is sort the string array, and compare the first and the last string.

Solution 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public String longestCommonPrefix(String[] strs) {
        if (strs.length == 0) return "";
        if (strs.length == 1) return strs[0];
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < strs[0].length(); i++) {
            char a = strs[0].charAt(i);
            for (int j = 1; j < strs.length; j++) {
                if (i >= strs[j].length() || a != strs[j].charAt(i)) {
                    return sb.toString();
                }
            }
            sb.append(a);
        }
        return sb.toString();
    }
}

Solution 2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public String longestCommonPrefix(String[] strs) {
        if (strs.length == 0) return "";
        if (strs.length == 1) return strs[0];
        Arrays.sort(strs);
        int minLen = 0;
        
        if (strs[0].length() < strs[strs.length-1].length()) {
            minLen = strs[0].length();
        } else {
            minLen = strs[strs.length-1].length();
        }
        int i = 0;
        while (i < minLen) {
            if (strs[0].charAt(i) == strs[strs.length-1].charAt(i)) {
                i++;
            } else {
                break;
            }
        }
        return strs[0].substring(0, i);
    }
}