14. Longest Common Prefix

Intuition

To find the longest common prefix among all strings in an array, we can take advantage of comparing characters at each position across all strings. Since we're looking for a common prefix from the beginning, the moment characters at a particular position don't match across strings, we can stop and return the prefix up to that point.

Complexity

Space Complexity	Time Complexity
$\text{O}(1)$	$\text{O}(nm)$

Code

public String longestCommonPrefix(String[] words) {
    // Initialize the maximum possible common prefix length as the length of the first word
    int lastMatchingIndex = words[0].length();

    // Compare the first word with each of the other words
    for (int i = 1; i < words.length; ++i) {
        // Reduce the comparison length to the minimum length of both current and previous words
        lastMatchingIndex = Math.min(words[i].length(), lastMatchingIndex);

        // Compare characters one by one up to the last known matching index
        for (int j = 0; j < lastMatchingIndex; ++j) {
            if (words[0].charAt(j) != words[i].charAt(j)) {
                // Mismatch found; update the last matching index and break
                lastMatchingIndex = j;
                break;
            }
        }
    }

    // Return the longest common prefix from the first word
    return words[0].substring(0, lastMatchingIndex);
}