Homepage | Alpha Codes

Longest Common Prefix Among Strings

Wed Mar 27 2024

Longest Common Prefix (Brute Force Approach):

This method meticulously generates all possible prefixes for each string, subsequently comparing these to identify the longest common prefix across the set. It leverages a double iteration process to first gather all prefixes and then to iteratively compare these across strings, gradually narrowing down to the longest shared prefix. This approach, while straightforward, is less efficient for large datasets due to its exhaustive comparison mechanism.

Optimized Longest Common Prefix:

Enhancing efficiency, this optimized approach identifies the shortest string in the array as the potential longest common prefix, given that the common prefix cannot be longer than the shortest string. It then iterates through each character of this shortest string, comparing it with corresponding characters in other strings. Upon encountering a mismatch, it immediately returns the common prefix found up to that point. This method significantly reduces the number of comparisons, making it a superior solution for larger datasets.

1let strs = ['flower', 'flow', 'flight'];
2
3const prefixGnerator = (str) => {
4  let elem = [];
5  for (let i = 0; i < str.length; i++) {
6    elem.push(str.substring(0, i + 1));
7  }
8  return elem;
9};
10
11let longestCommonPrefix = function (strs) {
12  if (strs.length === 0) return '';
13  let elem = [];
14  for (let i = 0; i < strs.length; i++) {
15    elem.push(prefixGnerator(strs[i]));
16  }
17  let smallest = Infinity;
18  for (let i = 0; i < strs.length; i++) {
19    if (elem[i].length < smallest) {
20      smallest = elem[i].length;
21    }
22  }
23
24  let j = 0;
25  let commonPrefix = [];
26
27  while (j < smallest) {
28    let i = 0;
29    let flag = true;
30    while (i < elem.length - 1) {
31      if (elem[i][j] !== elem[i + 1][j]) {
32        flag = false;
33      }
34      i++;
35    }
36    if (flag) {
37      commonPrefix.push(elem[i - 1][j]);
38    }
39
40    j++;
41  }
42  return commonPrefix[commonPrefix.length - 1];
43};
44
45const longestCommonPrefixOptimized = function (strs) {
46  if (strs.length === 0) return '';
47  let shortest = strs[0];
48  for (let str of strs) {
49    if (str.length < shortest.length) {
50      shortest = str;
51    }
52  }
53  for (let i = 0; i < shortest.length; i++) {
54    for (let str of strs) {
55      if (str[i] !== shortest[i]) {
56        return shortest.substring(0, i);
57      }
58    }
59  }
60  return shortest;
61};
62
63//TC : O(m * n^2)
64console.log(longestCommonPrefix(strs));
65//TC : O(S), where S is the sum of all characters in all strings
66console.log(longestCommonPrefixOptimized(strs));
67