Question

link

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

Stats

Frequency 1
Diffficulty 2
Adjusted Difficulty 1
Time to use ----------

Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)

Analysis

Straight-forward solution. Will not go into details.

However, there’s another more generalized LCP array which is solved by use of Trie.

Solution

The code explains itself.

My code

public class Solution {
    public String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0) {
            return "";
        }
        int p;
        for (p = 0; p < strs[0].length(); p++) {
            char c = strs[0].charAt(p);
            // check all strings in array strs
            for (int i = 0; i < strs.length; i++) {
                if (p == strs[i].length()) {
                    return strs[i];
                } else if (c != strs[i].charAt(p)) {
                    return strs[i].substring(0, p);
                }
            }
            // if all strings have the same prefix
            // continue checking it
        }
        // first string in array strs is the shortest common prefix
        return strs[0];
    }
}