การจับกลุ่มสตริงที่คล้ายกัน (Similar String Groups) ใน JavaScript

บทความนี้สาธิตการจับกลุ่มสตริงที่ "คล้ายกัน" (similar): สลับตัวอักษร 2 ตำแหน่งได้เท่ากัน หรือเท่ากันโดยตรง ความสัมพันธ์แบบ transitive

ตัวอย่าง

["tars","rats","arts","star"] -> 2 groups: {tars,rats,arts}, {star}

ตัวอย่างโค้ด

const arr = ["tars","rats","arts","star"];

const isSimilar = (str1, str2) => {
  const obj = {};
  let counter = 0;
  for (let i = 0; i < str1.length; i++) {
    if (str1[i] !== str2[i]) { counter++; }
    obj[str1[i]] = str2[i];
  }
  return counter === 2 ? true : false;
};

const similarStringGroup = (arr = []) => {
  const group = [[arr[0]]];
  for (let i = 1; i < arr.length; i++) {
    let match = false;
    for (let j = 0; j < group.length; j++) {
      for (let k = 0; k < group[j].length; k++) {
        const booleanMatch = isSimilar(group[j][k], arr[i]);
        if (booleanMatch) {
          group[j].push(arr[i]);
          match = true;
          break;
        }
      }
      if (match === true) { break; }
    }
    if (match === false) { group.push([arr[i]]); }
  }
  return group.length;
};

console.log(similarStringGroup(arr));

ผลลัพธ์

2

คำอธิบาย

isSimilar: นับตำแหน่งที่ต่างกัน ต้องมี exactly 2 ตำแหน่ง (swap ได้)

similarStringGroup: Union-Find approach แบบ naive O(n² * m) m = string length

Optimization: ใช้ Union-Find (Disjoint Set) พร้อม path compression