Longest Common Prefix

Problem

Write a function to find the longest common prefix string amongst an array of strings. The common prefix means prefix in each string
So for ["a", "bc", "bd"] result is "", cause they don't share a common prefix
Prefix can have more than one character

Solution

Clear Iterative Solution: O(n^2) time

public 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++) {
            while (strs[i].indexOf(prefix) != 0) prefix = prefix.substring(0, prefix.length() - 1);
        }
        return prefix;
    }
}

Analysis

We first set prefix as the first element in given strs
Then we loop from the second element and check if they share common prefix
If not, we reduce the prefix by dropping the last character in a while loop
At the end, we return what prefix left

results matching ""

    No results matching ""