leetcode之wordsearch

客官°小女子只卖身不卖艺 2022-06-03 08:22 74阅读 0赞

## Problem ##

Given a 2D board and a word, find if the word exists in the grid.

The word can be constructed from letters of sequentially adjacent cell, where “adjacent” cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.

For example,  
Given board =

[
      ['A','B','C','E'],
      ['S','F','C','S'],
      ['A','D','E','E']
    ]

word = “ABCCED”, -> returns true,

word = “SEE”, -> returns true,

word = “ABCB”, -> returns false.

## 思考 ##

自己考虑采用map记录每个位置的字母，遍历给定的单词字符，比较每个位置是否是相邻。但是不同位置可以出现相同字母，就比较棘手。

又想构建树，一个单词就是一条树中的一条路径。但是跟节点无法确定，如果遍历board每个节点都构造树，未免太麻烦。

## Solution ##

boolean exist(char[][] board, String word) {
            char[] w = word.toCharArray();
            for (int y = 0; y < board.length; y++) {
                for (int x = 0; x < board[y].length; x++) {
                    if (exist(board, y, x, w, 0))
                        return true;
                }
            }
            return false;
        }
    
        private boolean exist(char[][] board, int y, int x, char[] word, int i) {
            if (i == word.length) return true;
            if (y < 0 || x < 0 || y == board.length || x == board[y].length) return false;
            if (board[y][x] != word[i]) return false;
            board[y][x] ^= 256;
            boolean exist = exist(board, y, x + 1, word, i + 1)
                    || exist(board, y, x - 1, word, i + 1)
                    || exist(board, y + 1, x, word, i + 1)
                    || exist(board, y - 1, x, word, i + 1);
            board[y][x] ^= 256;
            return exist;
        }

查看了leetcode大神的解答。用了递归。

这里比较巧妙的是`board[y][x] ^= 256;`，利用异或操作为为每个位置的char记录是否被访问。字母的ascii码小于128，这里异或256即`10000000`，异或0即是本身，所以低位没变，但是高位改变，没有字母能和异或后的结果相等，也就达到了记录是否被访问的效果，节省空间还方便。