algoadvance

Leetcode 14. Longest Common Prefix

Problem Statement

The problem requires you to 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:

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

Clarifying Questions

1. Q: Can the input array be empty? A: Yes, if the input array is empty, the function should return an empty string.

2. Q: Are all strings in the array non-empty? A: The problem does not explicitly say, so we should handle the case where strings could potentially be empty.

3. Q: Can the strings contain special characters or be of varying lengths? A: Yes, the strings can contain any characters and have varying lengths.

4. Q: Is the function case-sensitive? A: Yes, the function should treat uppercase and lowercase characters as different characters (case-sensitive).

5. Q: What should be returned if strings share no common prefix? A: Return an empty string “”.

Strategy

1. Initial check: If the input array is empty, return an empty string.
2. Reference: Use the first string as a reference and compare it with the other strings.
3. Comparison:
   • For each character in the reference string:
     • Compare it with the corresponding character in other strings.
     • If all strings match the character, continue.
     • If any string has a mismatch (or is shorter), return the substring from the start to the current character.
4. Edge Case: If any string is empty or no common prefix exists, return an empty string.

Code Implementation

#include <iostream>
#include <vector>
#include <string>
using namespace std;

string longestCommonPrefix(vector<string>& strs) {
    if (strs.empty()) return "";  // Return empty string for empty input array

    string prefix = strs[0];  // Take the first string as the initial prefix

    for (size_t i = 1; i < strs.size(); ++i) {
        // Compare current prefix with each string
        while (strs[i].find(prefix) != 0) {
            // Shrink prefix until it matches the beginning of str[i]
            prefix = prefix.substr(0, prefix.length() - 1);
            if (prefix.empty()) return "";  // No common prefix
        }
    }
    
    return prefix;
}

int main() {
    vector<string> strs = {"flower", "flow", "flight"};
    cout << "Longest Common Prefix: " << longestCommonPrefix(strs) << endl;  // Output: "fl"
    return 0;
}

Time Complexity

• The worst-case time complexity is O(S), where S is the sum of all characters in all strings. This is because each comparison might require checking each character of each string.
• On each step, the comparison could potentially remove a character from the prefix, giving a worst-case of examining all characters.

Summary

The implementation tackles comparisons pairwise, optimizing by reducing the size of the prefix as soon as mismatch detected. This strategy covers edge cases like empty arrays and unequal lengths efficiently.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?