Question

How to find the longest shared prefix among all words in a string with TypeScript

Answer 1

// Extract alphabetic words (lowercased)
function extractWords(text: string): string[] {
  const matches: RegExpMatchArray | null = text.match(/[A-Za-z]+/g);

  return matches ? matches.map(w => w.toLowerCase()) : [];
}

// Build prefix → list of words that share that prefix
function groupByPrefixes(words: string[]): Record<string, string[]> {
  const groups: Record<string, string[]> = {};

  for (const w of words) {
    for (let i = 1; i <= w.length; i++) {
      const prefix = w.slice(0, i);

      if (!groups[prefix]) {
        groups[prefix] = [];
      }

      groups[prefix].push(w);
    }
  }

  return groups;
}

// Find the longest prefix that appears in 2+ words
function longestSharedPrefix(groups: Record<string, string[]>): string {
  let best: string = "";

  for (const prefix in groups) {
    const list = groups[prefix];

    if (list.length >= 2 && prefix.length > best.length) {
      best = prefix;
    }
  }

  return best;
}

// ------------------------------------------------------------
// Main
// ------------------------------------------------------------

const text =
  "The Lowly inhabitants of the lowland were surprised to see " +
  "the lower branches of the trees.";

const words: string[] = extractWords(text);
const groups: Record<string, string[]> = groupByPrefixes(words);
const prefix: string = longestSharedPrefix(groups);

if (prefix) {
  const group = groups[prefix];
  console.log("Longest shared prefix:");
  console.log(
    `${prefix} | prefix_len=${prefix.length} | group_count=${group.length} | [${group.join(", ")}]`
  );
} else {
  console.log("No shared prefix found.");
}




/*
run:

"Longest shared prefix:" 
"lowl | prefix_len=4 | group_count=2 | [lowly, lowland]"

*/

 

70+ SQL courses for beginners and professionals