LeetCode 14: Longest Common Prefix Solution

Master LeetCode problem 14 (Longest Common Prefix), a easy challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

14. Longest Common Prefix

Easy

String Trie

Problem Explanation

Explanation:

To find the longest common prefix among an array of strings, we can iterate through the characters of the first string and compare them with the corresponding characters of the other strings. The common prefix will be the characters that are the same at each position for all strings. If we encounter a character that is different, we can stop the iteration and return the prefix found so far. If there are no common characters at any position, we return an empty string.

Algorithm:

If the input array is empty, return an empty string.
Initialize the longest common prefix as the first string in the array.
Iterate through the characters of the first string.
For each character, compare it with the corresponding character of the other strings in the array.
If a character is different or the end of any string is reached, return the prefix found so far.
If the loop completes, return the prefix as the longest common prefix.

Time Complexity:

Let n be the number of strings in the input array and m be the average length of the strings.
The algorithm compares characters in each string, taking O(m*n) time in the worst case.
Hence, the time complexity is O(m*n).

Space Complexity:

The algorithm uses only a constant amount of extra space.
Hence, the space complexity is O(1).

Solution Code

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);
                if (prefix.isEmpty()) {
                    return "";
                }
            }
        }

        return prefix;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 14 (Longest Common Prefix)?

This page provides optimized solutions for LeetCode problem 14 (Longest Common Prefix) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 14 (Longest Common Prefix)?

The time complexity for LeetCode 14 (Longest Common Prefix) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 14 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 14 in Java, C++, or Python.

Back to LeetCode Solutions