DevExplained

14. Longest Common Prefix

StringTrie

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:

  1. If the input array is empty, return an empty string.
  2. Initialize the longest common prefix as the first string in the array.
  3. Iterate through the characters of the first string.
  4. For each character, compare it with the corresponding character of the other strings in the array.
  5. If a character is different or the end of any string is reached, return the prefix found so far.
  6. 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).

:

View Leetcode Problem
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;
    }
}

Code Editor (Testing phase)

Improve Your Solution

Use the editor below to refine the provided solution. Select a programming language and try the following:

  • Add import statement if required.
  • Optimize the code for better time or space complexity.
  • Add test cases to validate edge cases and common scenarios.
  • Handle error conditions or invalid inputs gracefully.
  • Experiment with alternative approaches to deepen your understanding.

Click "Run Code" to execute your solution and view the output. If errors occur, check the line numbers and debug accordingly. Resize the editor by dragging its bottom edge.

Previous QuestionNext Question