การค้นหาคำในเมทริกซ์ตัวอักษรด้วย JavaScript

บทความนี้สาธิตการค้นหาว่าสามารถสร้างคำ (word) จากเมทริกซ์ตัวอักษรได้หรือไม่ โดยเดินทางผ่าน adjacent cells (up/down/left/right) ไม่ซ้ำ cell

ตัวอย่าง

matrix = [['s','d','k','e'], ['j','m','o','w'], ['y','n','l']]
word = 'don' -> false

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

const arr = [
  ['s', 'd', 'k', 'e'],
  ['j', 'm', 'o', 'w'],
  ['y', 'n', 'l']
];
const str = 'don';

const containsWord = (arr = [], str = '') => {
  if (arr.length === 0) {
    return false;
  }
  const height = arr.length;
  const width = arr[0].length;
  const dirs = [[-1, 0], [0, 1], [1, 0], [0, -1]];
  const tryWord = (x, y, k) => {
    if (arr[x][y] !== str[k]) return false;
    if (k === str.length - 1) return true;
    arr[x][y] = '*';
    for (const [dx, dy] of dirs) {
      const i = x + dx;
      const j = y + dy;
      if (i >= 0 && i < height && j >= 0 && j < width) {
        if (tryWord(i, j, k + 1)) return true;
      }
    }
    arr[x][y] = str[k];
    return false;
  };
  for (let i = 0; i < height; i++) {
    for (let j = 0; j < width; j++) {
      if (tryWord(i, j, 0)) return true;
    }
  }
  return false;
};

console.log(containsWord(arr, str));

ผลลัพธ์

false

คำอธิบาย

DFS backtracking: ลองเริ่มจากทุก cell หากตรงตัวอักษรแรก ใส่ mark '*' แล้ว recursive 4 ทิศทาง

Time: O(m * n * 4^L) L = word length, Space: O(L) recursion stack

หมายเหตุ: โค้ดสมมติ matrix เป็น rectangle (ทุก row ยาวเท่ากัน) แต่ตัวอย่าง row 3 มีแค่ 3 elements อาจ error