14. Longest Common Prefix - Detailed Explanation

Problem Statement

Given an array of strings, write a function to find the longest common prefix string among them. If there is no common prefix, return an empty string "".

For example, if the input is ["flower", "flow", "flight"], the longest common prefix is "fl".

Examples

Example 1

• Input: ["flower", "flow", "flight"]
• Output: "fl"
• Explanation: The common prefix among all strings is "fl".

Example 2

• Input: ["dog", "racecar", "car"]
• Output: ""
• Explanation: There is no common prefix among the input strings, so the result is an empty string.

Approaches

There are multiple approaches to solve this problem:

1. Horizontal Scanning

• Idea:
  Start by assuming the first string is the common prefix. Then iterate through the remaining strings and update the common prefix by comparing it with each string.
• Process:
  • Initialize the prefix as the first string.
  • For each subsequent string, reduce the prefix until the string starts with the prefix.
  • If at any point the prefix becomes empty, return "".
• Time Complexity: O(S) where S is the sum of all characters in all strings.

2. Vertical Scanning

• Idea:
  Compare characters from top to bottom (column by column). For each character position, check if all strings have the same character at that position.
• Process:
  • For each character index, iterate through all strings.
  • If a mismatch is found or the end of one string is reached, return the prefix up to that point.
• Time Complexity: O(minLen * n), where minLen is the length of the shortest string and n is the number of strings.

3. Divide and Conquer

• Idea:
  Recursively split the list of strings into two halves, find the longest common prefix for each half, and then find the common prefix of the two halves.
• Time Complexity: O(S), similar to horizontal scanning.

4. Binary Search

• Idea:
  Use binary search on the length of the common prefix. Check if a prefix of a given length is common to all strings. Adjust the binary search boundaries based on the result.
• Time Complexity: O(n * minLen * log(minLen)).

In this explanation, we focus on the Horizontal Scanning method due to its simplicity and efficiency for typical input sizes.

Detailed Step-by-Step (Horizontal Scanning)

1. Initialize the Prefix:
   Assume the first string is the common prefix.

2. Iterate Over Strings:
   For each subsequent string:

   • While the current string does not start with the prefix:
     • Remove the last character from the prefix.
   • If the prefix becomes empty, return an empty string immediately.

3. Return the Result:
   After processing all strings, the prefix is the longest common prefix.

Python Code