Longest Common Prefix
LeetCode #14 · Easy · Strings · C++ solution with worked-out approach and complexity analysis.
Approach
Horizontal Scanning
Take the first string as the initial reference 'res'. Iterate through the rest of the strings. For each string, compare it with 'res' character by character and update 'res' to be the common substring found so far. If 'res' becomes empty, stop and return "".
Time
O(S)
S is the sum of all characters in all strings.
Space
O(1)
ignoring the space taken by the result.
Problem description(from LeetCode)
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 "".
Examples
Example 1
- Input:
- strs = ["flower","flow","flight"]
- Output:
- "fl"
- Note:
- There is no common prefix among the input strings.
Constraints
- •1 <= strs.length <= 200
- •0 <= strs[i].length <= 200
- •strs[i] consists of only lowercase English letters.
C++ Solution
solution.cpp
class Solution {
public:
string longestCommonPrefix(vector<string> &strs) {
string res = strs[0];
for (int i = 1, n = strs.size(); i < n; i++) {
int j = 0, m = min(strs[i].size(), res.size());
for (j = 0; j < m; j++) {
if (strs[i][j] != res[j]) break;
}
res = res.substr(0, j);
}
return res;
}
};