Longest Common Prefix in an Array of Strings

28
0

Given an array of strings strs, return the longest starting part, or prefix, shared by every string. Return an empty string "" if no common prefix exists.

Example 1

Input: strs = ["track", "train", "trace"]

Output: "tra"

Explanation: All three strings start with "tra", but their next letters do not all match.

Example 2

Input: strs = ["red", "blue", "green"]

Output: ""

Explanation: The strings start with different letters, so there is no common prefix.

Brute Force Approach

Strings with the same beginning appear together when arranged in dictionary order. After sorting, any prefix shared by the first and last strings must also appear at the beginning of every string between them. A string without that prefix would fall outside this group.

This means only the first and last strings need to be compared after sorting. Compare their letters from the beginning and continue while they match. Stop when the letters differ or either string ends. The part matched so far is the answer, because a longer prefix would fail to match even these two strings.

Algorithm

  • If the array is empty, return "".

  • Sort the strings in dictionary order.

  • Select the first and last strings from the sorted array.

  • Compare their characters at the same position, starting from the beginning.

  • Continue while the characters match and neither string has ended.

  • Return the matching starting part of the first string.

Dry Run

Longest common prefix in an array of strings - Brute

Longest common prefix in an array of strings - Brute

Solution

#include<bits/stdc++.h>
using namespace std;
class Solution {
public:
// Returns the longest prefix shared by all strings.
string longestCommonPrefix(vector<string>& strs) {
if (strs.empty()) {
return "";
}
// Arrange strings in dictionary order.
sort(strs.begin(), strs.end());
// Their common prefix is shared by every string between them.
const string& first = strs.front();
const string& last = strs.back();
int length = 0;
// Stop at a mismatch or the end of either string.
while (length < first.size() &&
length < last.size() &&
first[length] == last[length]) {
length++;
}
// Keep only the characters that matched from the beginning.
return first.substr(0, length);
}
};
// Driver code
int main() {
vector<string> strs = {"track", "train", "trace"};
// Create an instance of Solution.
Solution sol;
cout << sol.longestCommonPrefix(strs) << '\n';
return 0;
}

Complexity Analysis

Let N be the number of strings and M be the length of the longest string.

Time Complexity: O(N × M × log N) for comparison-based sorting. Sorting takes O(N log N) string comparisons, and each comparison may examine up to M characters. Comparing the first and last strings takes another O(M) time.

Space Complexity: Sorting space depends on the implementation: typically O(log N) in C++ and up to O(N) in Java and Python. JavaScript sorting space depends on the engine. The returned prefix can use another O(P) space, where P is its length.

Optimal Approach

A common prefix must match at every position from the beginning. So, the first character belongs to the answer only if every string has that character first. The second character can be included only if every string also agrees at the second position, and the same rule continues.

Use the first string as a reference and check one character position across all the other strings before moving to the next position. This is called vertical scanning, because the strings can be viewed as rows and their character positions as columns.

If any string has a different character at the current position, the common prefix ends just before it. The same applies when a string ends: a shared prefix cannot be longer than that string. If every character of the first string matches across all the strings, the entire first string is the answer.

Algorithm

  • If the array is empty, return "".

  • Take the first string as the reference.

  • Starting from its first character, check the same position in every other string.

  • If another string has already ended or contains a different character at that position, return the reference string’s prefix before that position.

  • Move to the next position only after every string matches at the current position.

  • If every position in the reference string matches, return the entire reference string.

Dry Run

Longest common prefix in an array of strings - Optimal

Longest common prefix in an array of strings - Optimal

Solution

#include<bits/stdc++.h>
using namespace std;
class Solution {
public:
// Returns the longest prefix shared by all strings.
string longestCommonPrefix(vector<string>& strs) {
if (strs.empty()) {
return "";
}
// Compare every other string against the first one.
const string& first = strs[0];
// Check one character position across all strings.
for (int index = 0; index < first.size(); index++) {
for (int row = 1; row < strs.size(); row++) {
// A shorter string or a different letter ends the prefix.
if (index >= strs[row].size() ||
strs[row][index] != first[index]) {
return first.substr(0, index);
}
}
}
// Every character of the first string matched.
return first;
}
};
// Driver code
int main() {
vector<string> strs = {"track", "train", "trace"};
// Create an instance of Solution.
Solution sol;
cout << sol.longestCommonPrefix(strs) << '\n';
return 0;
}

Complexity Analysis

Let N be the number of strings and M be the length of the longest string.

Time Complexity: O(N × M) in the worst case, since each character position may need to be checked across all strings. The scan stops as soon as a mismatch or the end of a string is found.

Space Complexity: O(1) extra space, excluding the returned prefix, which can take O(P) space for a prefix of length P.

Interview follow-up Questions

The answer is "". An empty string has no characters, so no non-empty prefix can be shared by every string.

StringSortingArraysTCS NQT

Read Similar Blogs

Comments0