[LeetCode] Longest Common Prefix (Java)

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

Analysis

This is a simple problem. We can just check for each position of every string in the string array. But we need to take care of some strings that is shorter than others.

Since there is two loops, we can break the outer loop if we found a mismatch or we have reached the end of certain string.

Code

public class Solution {
    public String longestCommonPrefix(String[] strs) {
        if (strs.length == 0)
            return new String("");
        if (strs.length == 1)
            return strs[0];
        StringBuilder prefix = new StringBuilder();
        char c = 0;
        outer:
        for (int p = 0; p < strs[0].length(); p++) {
            for (int i = 0; i < strs.length; i++) {
                if (p == strs[i].length())
                    break outer;
                if (i == 0) {
                    c = strs[i].charAt(p);
                } else {
                    if (strs[i].charAt(p) != c)
                        break outer;
                    if (i == strs.length - 1)
                        prefix.append(c);
                }
            }
        }
        return prefix.toString();
    }
}

public class Solution {

public String longestCommonPrefix(String[] strs) {

if (strs.length == 0)

return new String("");

if (strs.length == 1)

return strs[0];

StringBuilder prefix = new StringBuilder();

char c = 0;

outer:

for (int p = 0; p < strs[0].length(); p++) {

for (int i = 0; i < strs.length; i++) {

if (p == strs[i].length())

break outer;

if (i == 0) {

c = strs[i].charAt(p);

} else {

if (strs[i].charAt(p) != c)

break outer;

if (i == strs.length - 1)

prefix.append(c);

}

return prefix.toString();

}

Complexity

In the best case we need to check every character of each string. Assuming the average length of string is m, and there are n strings. Then the complexity is O(mn).