Sponsored
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.
1function
The JavaScript solution emulates a divide-and-conquer strategy, recursively simplifying the problem until it's possible to discover and merge the common prefix.