Tìm từ trong ma trận trong JavaScript

Chúng ta cần viết một hàm JavaScript nhận vào một mảng các mảng ký tự làm đối số đầu tiên và một chuỗi làm đối số thứ hai.

Hàm nên tìm xem có tồn tại các ký tự trong ma trận, tổ hợp không lặp lại của chúng cho ra chuỗi được cung cấp làm đối số thứ hai hay không.

Nếu tồn tại tổ hợp như vậy, hàm nên trả về true, ngược lại false.

Ví dụ:

Nếu mảng đầu vào và chuỗi là:

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

Thì đầu ra nên là:

const output = false;

Ví dụ

Dưới đây là mã nguồn:

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]; // reset       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));

Kết quả

Đầu ra trên console:

false

Giải thích: Word Search (LeetCode 79). DFS + backtracking từ mỗi ô. Đánh dấu visited bằng cách ghi đè tạm thời (sau đó restore). 4 hướng: lên, phải, xuống, trái. O(m*n*4^L) time, L = độ dài từ.