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.
1using System;
2class Solution {
3 public string LongestCommonPrefix(string[] strs) {
4 if (strs.Length == 0) return "";
5 string prefix = strs[0];
6 for (int i = 1; i < strs.Length; i++) {
7 while (strs[i].IndexOf(prefix) != 0) {
8 prefix = prefix.Substring(0, prefix.Length - 1);
9 if (prefix == "") return "";
10 }
11 }
12 return prefix;
13 }
14
15 static void Main(string[] args) {
16 var sol = new Solution();
17 string[] strs = { "flower", "flow", "flight" };
18 Console.WriteLine(sol.LongestCommonPrefix(strs));
19 }
20}Similar to other solutions, this implementation checks each string using IndexOf. The prefix is shortened as needed to maintain a common prefix.
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#include <vector>
using namespace std;
string commonPrefix(string left, string right) {
int minLength = min(left.size(), right.size());
for (int i = 0; i < minLength; i++) {
if (left[i] != right[i]) {
return left.substr(0, i);
}
}
return left.substr(0, minLength);
}
string divideAndConquer(vector<string>& strs, int left, int right) {
if (left == right) {
return strs[left];
} else {
int mid = (left + right) / 2;
string lcpLeft = divideAndConquer(strs, left, mid);
string lcpRight = divideAndConquer(strs, mid + 1, right);
return commonPrefix(lcpLeft, lcpRight);
}
}
string longestCommonPrefix(vector<string>& strs) {
if (strs.empty()) return "";
return divideAndConquer(strs, 0, strs.size() - 1);
}
int main() {
vector<string> strs = { "flower", "flow", "flight" };
cout << longestCommonPrefix(strs) << endl;
return 0;
}The C++ program functions akin to C but leverages the standard library for ease. Recursion divides and resolves prefix comparisons, achieving efficiency with a hierarchical breakdown.