Question

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

Answer 1

// Extract alphabetic words (lowercased)
function extractWords(text) {
  return text
    .match(/[A-Za-z]+/g)
    .map(w => w.toLowerCase());
}

// Build prefix → list of words that share that prefix
function groupByPrefixes(words) {
  const groups = {};

  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) {
  let best = "";

  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 = extractWords(text);
const groups = groupByPrefixes(words);
const prefix = 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