Longest Common Prefix

The Longest Common Prefix problem is a classic challenge that has stumped many, but fear not: with the right approach, it can be conquered. In this article, we'll explore several methods for solving the Longest Common Prefix problem, from the brute force approach to a more efficient Trie-based solution. So grab your keyboard and let's dive in!"

Problem Statement:

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 "".

---

Approach 1: Brute Force

1. We will start with the first string and compare its characters with the corresponding characters of all other strings.

2. We will use two nested loops, with the outer loop iterating over the characters of the first string, and the inner loop iterating over all the other strings.

3. The common prefix is found when a mismatch is encountered or when the end of any string is reached.

// ES6 Arrow Function
const longestCommonPrefix = strs => {
    if(strs.length === 0 || strs === null) return '';

    let prefix = '';
    for(let i = 0; i < strs[0].length; i++) {
        const char = strs[0][i];

        for(let j = 1; j < strs.length; j++) {
            if(i >= strs[j].length || strs[j][i] !== char) {
                return prefix;
            }
        }

        prefix += char;
    }

    return prefix;
}

Time Complexity: O(N * M), where N is the number of strings and M is the length of the longest string.

Space Complexity: O(1)

---

Approach 2: Sorting

1. In this approach, we sort the strings and compare the first and last strings in the sorted list.

2. Since the longest common prefix must be a prefix of all strings, the common prefix of the first and last strings is also the common prefix of all strings.

// ES6 Arrow Function
const longestCommonPrefix = strs => {
    //base case
    if(strs.length === 0 || strs === null) return '';

    strs.sort();

    let first = strs[0], last = strs[strs.length - 1];
    let prefix = '';

    for(let i = 0; i < first.length; i++) {
        if(first[i] !== last[i]) break;
        prefix += first[i];
    }

    return prefix;

}

Time Complexity: O(N*M log M), where N is the number of strings and M is the length of the longest string.

Note: Sorting takes O(N log N) time, and comparing the first and last strings takes O(M) time.

Space Complexity: O(1)

---

Approach 3: Trie

The trie data structure is a tree-like structure that is used to store a set of strings. Each node of the tree represents a prefix of one or more strings in the set, and the edges represent the characters that follow the prefix. The nodes that correspond to complete strings have a flag or a special character to indicate that they are the end of a string.

The basic idea of using trie to solve the longest common prefix problem is to find the common prefix by traversing the trie from the root to the deepest node that has more than one child or is the end of a string. The common prefix is the characters that appear along the path from the root to that node.

1. Create a new Trie object.

2. Insert all the strings in the input array into the Trie.

3. Traverse the Trie from the root to the deepest node that has more than one child or is the end of a string, and record the characters along the way.

4. Return the recorded characters as the longest common prefix.

// ES6 Arrow Function
class TrieNode {
  constructor() {
    this.children = new Map();
    this.isEndOfWord = false;
  }
}

class Trie {
  constructor() {
    this.root = new TrieNode();
  }

  insert(word) {
    let node = this.root;
    for (let i = 0; i < word.length; i++) {
      const char = word[i];
      if (!node.children.has(char)) {
        node.children.set(char, new TrieNode());
      }
      node = node.children.get(char);
    }
    node.isEndOfWord = true;
  }

  longestCommonPrefix() {
    let node = this.root;
    let prefix = "";
    while (node.children.size === 1 && !node.isEndOfWord) {
      const char = node.children.keys().next().value;
      prefix += char;
      node = node.children.get(char);
    }
    return prefix;
  }
}

function longestCommonPrefix(strs) {
  // base case
  if (strs.length === 0 || strs === null) return "";

  const trie = new Trie();
  for (const word of strs) {
    trie.insert(word);
  }

  return trie.longestCommonPrefix();
}

Time Complexity: O(MN), where m is the average length of the strings and n is the number of strings in the input array.

Space Complexity: O(MN)

---

And there you have it, folks — we’ve explored various approaches to solving the Longest Common Prefix problem, from the brute force method to the Trie solution. Whether you prefer to tackle problems head-on or take a more organized approach, there’s always a way to solve a problem. So go forth and code with confidence, and remember: when in doubt, try turning it off and on again (just kidding, don’t do that 😉).

Problem - Leetcode 19