Intuition

This problem is about finding the longest common prefix among a set of strings. The common prefix is the longest string that is a prefix of all strings in the set. For example, given the set of strings {“flower”, “flow”, “flight”}, the longest common prefix is “fl”. To solve this problem, we can iterate through the strings and try to find if the prefix is in the first string. If it is not, we remove the last character from the prefix and try again. We continue this process until we find the longest common prefix. If we reach the end of the strings without finding a common prefix, we return an empty string.

Approach

1. Initialize a variable prefix to the first string in the vector.
2. Iterate through the vector of strings.
3. For each string, check if the prefix is found at the beginning by using string::find(). If it is not, remove the last character from the prefix and try again.
4. If we reach the end of the strings without finding a common prefix, return an empty string.

Complexity

• Time complexity:
  Let n = number of strings, and m = length of the first string (worst-case prefix length).
  For each string, in the worst case we may shrink the prefix character by character. Checking find(prefix) costs up to O(L) where L is the length of the current string. So the total complexity is:
  O(n * m * L) in the naive analysis.
  However, since prefix shrinks across iterations, the tighter bound is O(n * m), where m is the length of the shortest string.

• Space complexity:
  O(1) (ignoring the prefix storage, which is at most the length of the first string).

Code

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        std::string prefix = strs[0];

        for(size_t i = 0; i < strs.size(); i++){
            while(strs[i].find(prefix) != 0){
                prefix = prefix.substr(0, prefix.size() - 1);
                if(prefix.empty()) return "";
            }
        }
        return prefix;
    }
};