LeetCode 14 Solution

Problem Statement (LeetCode 14 - Longest Common Prefix)

Write a function to find the longest common prefix string amongst an array of strings.

If there is no common prefix, return an empty string "".

Example 1:

Input: strs = ["flower","flow","flight"]
Output: "fl"

Example 2:

Input: strs = ["dog","racecar","car"]
Output: ""
Explanation: There is no common prefix among the input strings.

---

Optimal Approach: Horizontal Scanning

Intuition

1. Start by assuming that the entire first string is the longest common prefix.
2. Iterate through the rest of the strings and compare each one with the current common prefix.
3. Shorten the common prefix until it matches the start of each string.

Why This Approach Works

• Efficient Iteration: We compare each string with the current longest common prefix, reducing the number of comparisons by eliminating non-matching portions quickly.
• Time Efficiency: By scanning each string linearly and reducing the prefix step-by-step, we ensure that the solution is efficient.

---

LeetCode-Compatible C++ Code

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        // Edge case: if the array is empty, return an empty string
        if (strs.empty()) return "";
        
        // Assume the first string is the common prefix
        string prefix = strs[0];
        
        // Compare the prefix with all other strings
        for (int i = 1; i < strs.size(); ++i) {
            // Compare prefix with current string
            int j = 0;
            while (j < prefix.size() && j < strs[i].size() && prefix[j] == strs[i][j]) {
                ++j;
            }
            // Update the prefix to the common part of prefix and current string
            prefix = prefix.substr(0, j);
            if (prefix == "") return "";  // No common prefix found
        }
        
        return prefix;
    }
};

---

Step-by-Step Explanation of Code

1. Edge Case Handling:
   If the input vector strs is empty, we immediately return an empty string since no common prefix can exist.

2. Initialize Prefix:
   We assume that the first string in the array is the longest common prefix (prefix = strs[0]).

3. Iterate Through the Strings:

   • For each subsequent string in the array, we compare it with the current prefix.
   • We use a pointer j to iterate through both the prefix and the current string simultaneously, checking for matching characters.
   • Once a mismatch is found, we update the prefix to the substring that matches the current string (i.e., prefix = prefix.substr(0, j)).

4. Early Termination:
   If at any point, the prefix becomes empty (prefix == ""), we immediately return it, as it indicates no common prefix exists.

5. Return Result:
   After processing all strings, we return the longest common prefix.

---

Dry Run with Example

Input: strs = ["flower", "flow", "flight"]

Step 1: Initialize prefix as "flower"
Step 2: Compare "flower" with "flow":
        - Compare characters: f == f, l == l, o == o, w == w
        - Mismatch at character 'e' and 'w', update prefix to "flow"
Step 3: Compare "flow" with "flight":
        - Compare characters: f == f, l == l, o != i
        - Mismatch at character 'o' and 'i', update prefix to "fl"
Final result: "fl"

✅ Output: "fl"

---

Alternative Approaches & Why Not?

Approach	Time Complexity	Space Complexity	Why Not?
Brute Force (Compare All Pairs)	O(n*m)	O(1)	Inefficient as we are comparing every pair of strings, resulting in unnecessary redundant comparisons.
Sorting and Comparing Adjacent Strings	O(n log n + n*m)	O(1)	Sorting strings adds an extra O(log n) complexity, which is not needed.
Vertical Scanning	O(n*m)	O(1)	Similar time complexity as horizontal scanning but requires handling each column individually, which is less intuitive.

---

Why Horizontal Scanning is the Best

1. Time Complexity is Linear: We only scan each string once, and each comparison with the prefix is done linearly, resulting in O(n * m) time complexity where n is the number of strings and m is the length of the shortest string.
2. Space Complexity is Constant: We only use a few variables and the substring method, keeping space complexity at O(1).
3. Simplicity: The approach is simple to understand and implement while ensuring optimal time complexity.

---

Complexity Analysis

• Time Complexity: O(n * m)
  Where n is the number of strings and m is the average length of the strings. Each string is compared character-by-character to the current prefix.

• Space Complexity: O(1)
  The space complexity is constant since only a few extra variables are used (the prefix and loop counters).

---

Conclusion

✅ Best Approach: Horizontal Scanning
✅ Time Complexity: O(n * m)
✅ Space Complexity: O(1)
✅ Optimal Solution for the Problem

Recommended Problems for Practice

1. Group Anagrams 🧩
2. Valid Anagram 🔠
3. Longest Palindromic Prefix 🏅

🚀 Master Prefix Matching with Horizontal Scanning!