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.
Constraints:
1 <= strs.length <= 2000 <= strs[i].length <= 200strs[i] consists of only lowercase English letters.The Longest Common Prefix problem asks you to find the longest starting substring shared by all strings in an array. A common way to think about this is by comparing characters position by position across all strings until a mismatch appears.
One intuitive method is horizontal scanning. Start with the first string as a candidate prefix and progressively compare it with each subsequent string, shrinking the prefix whenever characters stop matching. This works efficiently because the prefix only gets shorter as comparisons continue.
Another useful idea is sorting the array and comparing only the first and last strings. Since sorting places lexicographically similar strings close together, the common prefix of these two extremes reflects the prefix shared by the whole list.
For learning purposes, you can also model the strings using a Trie (prefix tree). By inserting all words and traversing nodes that have only one child, you can determine the shared prefix structure. Typical solutions run in O(N * M) time where N is the number of strings and M is the average string length.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Horizontal Scanning | O(N * M) | O(1) |
| Sorting + First/Last Comparison | O(N log N * M) | O(1) |
| Trie (Prefix Tree) | O(N * M) | O(N * M) |
NeetCode
In this approach, you start with the first string as a reference and gradually compare it with each subsequent string in the array. The reference prefix is shortened until it matches the prefixes of all strings.
Time Complexity: O(S), where S is the sum of all characters in all strings.
Space Complexity: O(1), as we are using constant extra space.
1#include <stdio.h>
2#include <string.h>
3
4char* longestCommonPrefix(char** strs, int strsSize) {
5 if (strsSize == 0) return "";
6 char* prefix = strs[0];
7 for (int i = 1; i < strsSize; i++) {
8 while (strstr(strs[i], prefix) != strs[i]) {
9 prefix[strlen(prefix) - 1] = '\0';
10 if (*prefix == '\0') return "";
11 }
12 }
13 return prefix;
14}
15
16int main() {
17 char *strs[] = { "flower", "flow", "flight" };
18 printf("%s\n", longestCommonPrefix(strs, 3));
19 return 0;
20}This implementation starts by taking the first string as the initial prefix. It iteratively checks if this prefix is valid for each string, adjusting it until all strings have a common start. If a mismatch occurs, we shorten the prefix from the end.
This approach involves dividing the array of strings into two halves, recursively finding the longest common prefix for each half, and merging the results. The merge step compares characters from the two strings to find the common prefix.
Time Complexity: O(S), where S is the sum of all characters in the strings.
Space Complexity: O(M*logN), where M is the length of the common prefix and N is the number of strings.
1#
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, Longest Common Prefix is a common introductory string problem asked in technical interviews, including FAANG-style interviews. It tests understanding of string manipulation, edge cases, and basic algorithm design.
A Trie (prefix tree) is a natural data structure for prefix-related problems. By inserting all strings and traversing nodes that have only one child, you can identify the shared prefix among all words. However, for interview settings, simpler string comparison approaches are often preferred.
A common optimal approach is horizontal scanning. Start with the first string as the prefix and compare it with each subsequent string, trimming the prefix whenever characters differ. This keeps the solution simple and runs in O(N * M) time where N is the number of strings and M is the prefix length.
Yes, sorting the array of strings can simplify the problem. After sorting, you only need to compare the first and last strings because they will represent the maximum possible difference in prefixes. Their shared prefix will match the common prefix of the entire array.
This C solution reduces the problem into finding the longest common prefix of smaller sections, leading to a combination of results using a helper function to merge prefixes by character comparison.