212. Word Search II

原题：212. Word Search II

方法一

思路

DFS。这道题借用了 79. Word Search 中的exist方法。

source code

// RuRuntime: 1352 ms, faster than 20.07% of JavaScript online submissions for Word Search II.
// Memory Usage: 45 MB, less than 100.00% of JavaScript online submissions for Word Search II.
var exist = function (board, word) {
  const helper = function (i, j, w) {
    if (w >= word.length) {
      return true;
    }
    if (i < 0 || j < 0 || i >= board.length || j >= board[0].length) {
      //越界
      return false;
    }
    if (board[i][j] != word[w]) {
      return false;
    }
    //backtrace
    const tmp = board[i][j];
    board[i][j] = "*";
    if (
      helper(i - 1, j, w + 1) ||
      helper(i, j + 1, w + 1) ||
      helper(i + 1, j, w + 1) ||
      helper(i, j - 1, w + 1)
    ) {
      //上右下左
      return true;
    } else {
      board[i][j] = tmp;
      return false;
    }
  };

  if (!board || !board.length || !word) {
    //sanity check
    return false;
  }

  for (let i = 0; i < board.length; i++) {
    for (let j = 0; j < board[0].length; j++) {
      if (helper(i, j, 0)) {
        return true;
      }
    }
  }

  return false;
};

var findWords = function (board, words) {
  return words.filter((word) => exist(JSON.parse(JSON.stringify(board)), word));
};

方法二

思路

Trie。

//todo

test case

const board = [
  ["o", "a", "a", "n"],
  ["e", "t", "a", "e"],
  ["i", "h", "k", "r"],
  ["i", "f", "l", "v"],
];

test("test1", () => {
  expect(findWords(board, ["oath", "pea", "eat", "rain"]).sort()).toEqual(
    ["eat", "oath"].sort()
  );
});