Horizontal & Vertical Scanning: The Longest Common Prefix Problem

In the realm of strings and algorithms, the task of identifying the longest common prefix among an array of strings is one that has both practical and academic appeal. This type of functionality comes up more often than you might think in typeahead type search interfaces, or in bioinformatics, where common prefixes can be indicative of related sequences.

Here, I'd like to tackle this problem using two primary methods that any developer should be familiar with: Horizontal Scanning and Vertical Scanning, elucidated in TypeScript.

Understanding the Problem

Given an array of strings, find the longest common prefix (LCP) amongst all the strings. If there is no common prefix, return an empty string: "".

Some Examples

Sometimes, it is easier to see the examples, so to offer some examples:

• For the strings ["apple", "applied", "applause"], the LCP is "appl";
• For the strings ["book", "boon", "bootcamp"], the LCP is "boo";
• For the strings ["car", "bus", "train"], the output is "" because there is no common prefix.

Solve Using Horizontal Scanning

The Concept

Horizontal Scanning involves taking the first string as a reference and comparing it with the next string until a common prefix for both is found. This prefix is then taken as the reference for the next comparison, and so on.

In Code

const longestCommonPrefix = (strs: string[]): string => {  if (strs.length === 0) return '';  let prefix = strs[0];  for (let i = 1; i < strs.length; i++) {    while (strs[i].indexOf(prefix) !== 0) {      prefix = prefix.substring(0, prefix.length - 1);      if (prefix === '') return '';    }  }  return prefix;};

How It Works

1. We initialise the prefix with the first string in the array.
2. We then loop over the other strings, constantly refining our prefix.
3. If at any point, the prefix is an empty string, we return "".

Solve Using Vertical Scanning

The Concept

Instead of comparing strings individually, we compare characters at the same position (index) across the strings. This way, we vertically scan through the array.

In Code

const longestCommonPrefix = (strs: string[]): string => {  if (strs.length === 0 || strs[0] === '') return '';  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 strs[0].substring(0, i);      }    }  }  return strs[0];};

How It Works

1. We loop over the characters of the first string.
2. For each character, we then check if the same character exists at the same index in all other strings.
3. If not, we return the prefix up to the current index.

Comparing the Two Methods

Horizontal Scanning: This is most efficient when the inputs are short. However, in a worst‑case scenario, it can result in S comparisons, where S is the sum of all characters in all strings.

Vertical Scanning: Although slower in some instances than Horizontal Scanning, this method performs more consistently, and can be much quicker where the matching prefixes are short.

Closing Thoughts

While both techniques have their strengths, it's crucial to understand the underlying nature of your data and choose wisely. May your strings always find their common ground!