题目: 单词搜索

来自智得网
跳转至： 导航、​ 搜索

方法一：回溯法

回溯法是解决单词搜索问题的常见方法。它通过深度优先搜索（DFS）的方式遍历矩阵中的每个位置，逐步构建单词，并进行回溯。具体步骤如下：

  1. 遍历矩阵中的每个位置，作为单词的起点。
  2. 对于每个起点位置，使用深度优先搜索进行回溯，判断当前位置是否匹配单词的第一个字母。
  3. 若匹配，则继续向上、下、左、右四个方向进行搜索，递归调用回溯函数。
  4. 在搜索过程中，判断当前位置是否越界、是否已经访问过、是否匹配当前单词字符等条件。
  5. 若遍历到单词的最后一个字符，且所有字符都匹配成功，则找到了目标单词，返回true。
  6. 若所有起点位置都搜索完毕，仍未找到目标单词，则返回false。
class Solution {
public:
    bool exist(vector<vector<char>>& board, string word) {
        if (board.empty() || board[0].empty()) return false;
        
        int m = board.size();
        int n = board[0].size();
        vector<vector<bool>> visited(m, vector<bool>(n, false));
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (dfs(board, word, visited, i, j, 0)) {
                    return true;
                }
            }
        }
        
        return false;
    }
    
private:
    bool dfs(vector<vector<char>>& board, string& word, vector<vector<bool>>& visited, int i, int j, int k) {
        if (k == word.length()) return true;
        if (i < 0 || i >= board.size() || j < 0 || j >= board[0].size() || visited[i][j] || board[i][j] != word[k]) {
            return false;
        }
        
        visited[i][j] = true;
        bool res = dfs(board, word, visited, i - 1, j, k + 1) ||
                   dfs(board, word, visited, i + 1, j, k + 1) ||
                   dfs(board, word, visited, i, j - 1, k + 1) ||
                   dfs(board, word, visited, i, j + 1, k + 1);
        visited[i][j] = false;
        
        return res;
    }
};

class Solution {
    public boolean exist(char[][] board, String word) {
        if (board == null || board.length == 0 || board[0].length == 0) return false;
        
        int m = board.length;
        int n = board[0].length;
        boolean[][] visited = new boolean[m][n];
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (dfs(board, word, visited, i, j, 0)) {
                    return true;
                }
            }
        }
        
        return false;
    }
    
    private boolean dfs(char[][] board, String word, boolean[][] visited, int i, int j, int k) {
        if (k == word.length()) return true;
        if (i < 0 || i >= board.length || j < 0 || j >= board[0].length || visited[i][j] || board[i][j] != word.charAt(k)) {
            return false;
        }
        
        visited[i][j] = true;
        boolean res = dfs(board, word, visited, i - 1, j, k + 1) ||
                      dfs(board, word, visited, i + 1, j, k + 1) ||
                      dfs(board, word, visited, i, j - 1, k + 1) ||
                      dfs(board, word, visited, i, j + 1, k + 1);
        visited[i][j] = false;
        
        return res;
    }
}

func exist(board [][]byte, word string) bool {
    if len(board) == 0 || len(board[0]) == 0 {
        return false
    }
    
    m, n := len(board), len(board[0])
    visited := make([][]bool, m)
    for i := 0; i < m; i++ {
        visited[i] = make([]bool, n)
    }
    
    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            if dfs(board, word, visited, i, j, 0) {
                return true
            }
        }
    }
    
    return false
}

func dfs(board [][]byte, word string, visited [][]bool, i, j, k int) bool {
    if k == len(word) {
        return true
    }
    if i < 0 || i >= len(board) || j < 0 || j >= len(board[0]) || visited[i][j] || board[i][j] != word[k] {
        return false
    }
    
    visited[i][j] = true
    res := dfs(board, word, visited, i-1, j, k+1) ||
           dfs(board, word, visited, i+1, j, k+1) ||
           dfs(board, word, visited, i, j-1, k+1) ||
           dfs(board, word, visited, i, j+1, k+1)
    visited[i][j] = false
    
    return res
}

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        if not board or not board[0]:
            return False
        
        m, n = len(board), len(board[0])
        visited = [[False] * n for _ in range(m)]
        
        for i in range(m):
            for j in range(n):
                if self.dfs(board, word, visited, i, j, 0):
                    return True
        
        return False
    
    def dfs(self, board, word, visited, i, j, k):
        if k == len(word):
            return True
        if i < 0 or i >= len(board) or j < 0 or j >= len(board[0]) or visited[i][j] or board[i][j] != word[k]:
            return False
        
        visited[i][j] = True
        res = self.dfs(board, word, visited, i - 1, j, k + 1) or \
              self.dfs(board, word, visited, i + 1, j, k + 1) or \
              self.dfs(board, word, visited, i, j - 1, k + 1) or \
              self.dfs(board, word, visited, i, j + 1, k + 1)
        visited[i][j] = False
        
        return res

var exist = function(board, word) {
    if (!board || !board.length || !board[0].length) return false;
    
    const m = board.length;
    const n = board[0].length;
    const visited = Array.from(Array(m), () => Array(n).fill(false));
    
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (dfs(board, word, visited, i, j, 0)) {
                return true;
            }
        }
    }
    
    return false;
};

const dfs = (board, word, visited, i, j, k) => {
    if (k === word.length) return true;
    if (i < 0 || i >= board.length || j < 0 || j >= board[0].length || visited[i][j] || board[i][j] !== word.charAt(k)) {
        return false;
    }
    
    visited[i][j] = true;
    const res = dfs(board, word, visited, i - 1, j, k + 1) ||
                dfs(board, word, visited, i + 1, j, k + 1) ||
                dfs(board, word, visited, i, j - 1, k + 1) ||
                dfs(board, word, visited, i, j + 1, k + 1);
    visited[i][j] = false;
    
    return res;
};

方法二：Trie树（前缀树）

Trie树是一种专门用于解决字符串匹配问题的数据结构。它通过构建多叉树的形式，将字符串按字符逐层存储，从而快速定位和搜索目标字符串。具体步骤如下：

  1. 构建Trie树：将所有目标单词插入到Trie树中，每个节点表示一个字符。
  2. 遍历矩阵中的每个位置，作为单词的起点。
  3. 对于每个起点位置，判断当前位置的字符是否存在于Trie树的根节点中。
  4. 若存在，则从当前位置开始，向上、下、左、右四个方向进行深度优先搜索，同时在Trie树中移动到下一个字符节点。
  5. 在搜索过程中，判断当前位置是否越界、是否已经访问过、是否匹配当前Trie树节点等条件。
  6. 若遍历到单词的最后一个字符，且所有字符都匹配成功，则找到了目标单词，返回true。
  7. 若所有起点位置都搜索完毕，仍未找到目标单词，则返回false。
class Solution {
public:
    bool exist(vector<vector<char>>& board, string word) {
        if (board.empty() || board[0].empty()) {
            return false;
        }
        
        int m = board.size();
        int n = board[0].size();
        vector<vector<bool>> visited(m, vector<bool>(n, false));
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (dfs(board, word, visited, i, j, 0)) {
                    return true;
                }
            }
        }
        
        return false;
    }
    
    bool dfs(vector<vector<char>>& board, string& word, vector<vector<bool>>& visited, int i, int j, int k) {
        if (k == word.length()) {
            return true;
        }
        if (i < 0 || i >= board.size() || j < 0 || j >= board[0].size() || visited[i][j] || board[i][j] != word[k]) {
            return false;
        }
        
        visited[i][j] = true;
        bool res = dfs(board, word, visited, i - 1, j, k + 1) ||
                   dfs(board, word, visited, i + 1, j, k + 1) ||
                   dfs(board, word, visited, i, j - 1, k + 1) ||
                   dfs(board, word, visited, i, j + 1, k + 1);
        visited[i][j] = false;
        
        return res;
    }
};

class Solution {
    public boolean exist(char[][] board, String word) {
        if (board == null || board.length == 0 || board[0].length == 0) {
            return false;
        }
        
        int m = board.length;
        int n = board[0].length;
        boolean[][] visited = new boolean[m][n];
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (dfs(board, word, visited, i, j, 0)) {
                    return true;
                }
            }
        }
        
        return false;
    }
    
    private boolean dfs(char[][] board, String word, boolean[][] visited, int i, int j, int k) {
        if (k == word.length()) {
            return true;
        }
        if (i < 0 || i >= board.length || j < 0 || j >= board[0].length || visited[i][j] || board[i][j] != word.charAt(k)) {
            return false;
        }
        
        visited[i][j] = true;
        boolean res = dfs(board, word, visited, i - 1, j, k + 1) ||
                      dfs(board, word, visited, i + 1, j, k + 1) ||
                      dfs(board, word, visited, i, j - 1, k + 1) ||
                      dfs(board, word, visited, i, j + 1, k + 1);
        visited[i][j] = false;
        
        return res;
    }
}

func exist(board [][]byte, word string) bool {
    if len(board) == 0 || len(board[0]) == 0 {
        return false
    }
    
    m := len(board)
    n := len(board[0])
    visited := make([][]bool, m)
    for i := 0; i < m; i++ {
        visited[i] = make([]bool, n)
    }
    
    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            if dfs(board, word, visited, i, j, 0) {
                return true
            }
        }
    }
    
    return false
}

func dfs(board [][]byte, word string, visited [][]bool, i, j, k int) bool {
    if k == len(word) {
        return true
    }
    if i < 0 || i >= len(board) || j < 0 || j >= len(board[0]) || visited[i][j] || board[i][j] != word[k] {
        return false
    }
    
    visited[i][j] = true
    res := dfs(board, word, visited, i-1, j, k+1) ||
           dfs(board, word, visited, i+1, j, k+1) ||
           dfs(board, word, visited, i, j-1, k+1) ||
           dfs(board, word, visited, i, j+1, k+1)
    visited[i][j] = false
    
    return res
}

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        if not board or not board[0]:
            return False
        
        m, n = len(board), len(board[0])
        visited = [[False] * n for _ in range(m)]
        
        for i in range(m):
            for j in range(n):
                if self.dfs(board, word, visited, i, j, 0):
                    return True
        
        return False
    
    def dfs(self, board, word, visited, i, j, k):
        if k == len(word):
            return True
        if i < 0 or i >= len(board) or j < 0 or j >= len(board[0]) or visited[i][j] or board[i][j] != word[k]:
            return False
        
        visited[i][j] = True
        res = self.dfs(board, word, visited, i - 1, j, k + 1) or \
              self.dfs(board, word, visited, i + 1, j, k + 1) or \
              self.dfs(board, word, visited, i, j - 1, k + 1) or \
              self.dfs(board, word, visited, i, j + 1, k + 1)
        visited[i][j] = False
        
        return res

var exist = function(board, word) {
    if (!board || !board.length || !board[0].length) {
        return false;
    }
    
    let m = board.length;
    let n = board[0].length;
    let visited = new Array(m).fill(false).map(() => new Array(n).fill(false));
    
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (dfs(board, word, visited, i, j, 0)) {
                return true;
            }
        }
    }
    
    return false;
};

var dfs = function(board, word, visited, i, j, k) {
    if (k === word.length) {
        return true;
    }
    if (i < 0 || i >= board.length || j < 0 || j >= board[0].length || visited[i][j] || board[i][j] !== word.charAt(k)) {
        return false;
    }
    
    visited[i][j] = true;
    let res = dfs(board, word, visited, i - 1, j, k + 1) ||
              dfs(board, word, visited, i + 1, j, k + 1) ||
              dfs(board, word, visited, i, j - 1, k + 1) ||
              dfs(board, word, visited, i, j + 1, k + 1);
    visited[i][j] = false;
    
    return res;
};

方法三：DFS + 剪枝

在回溯法的基础上，通过剪枝操作来提前终止无效搜索，提高效率。具体步骤如下：

  1. 遍历矩阵中的每个位置，作为单词的起点。
  2. 对于每个起点位置，使用深度优先搜索进行回溯，判断当前位置是否匹配单词的第一个字母。
  3. 若匹配，则继续向上、下、左、右四个方向进行搜索，递归调用回溯函数。
  4. 在搜索过程中，判断当前位置是否越界、是否已经访问过、是否匹配当前单词字符等条件。
  5. 在每次递归调用时，判断剩余单词是否能够在当前位置的周围找到，若不能找到，则进行剪枝操作，提前结束搜索。
  6. 在搜索过程中，若已经找到目标单词，则直接返回true。
  7. 若所有起点位置都搜索完毕，仍未找到目标单词，则返回false。
class Solution {
public:
    bool exist(vector<vector<char>>& board, string word) {
        if (board.empty() || board[0].empty()) {
            return false;
        }
        
        int m = board.size();
        int n = board[0].size();
        vector<vector<bool>> visited(m, vector<bool>(n, false));
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (dfs(board, word, visited, i, j, 0)) {
                    return true;
                }
            }
        }
        
        return false;
    }
    
    bool dfs(vector<vector<char>>& board, string word, vector<vector<bool>>& visited, int i, int j, int k) {
        if (k == word.size()) {
            return true;
        }
        if (i < 0 || i >= board.size() || j < 0 || j >= board[0].size() || visited[i][j] || board[i][j] != word[k]) {
            return false;
        }
        
        visited[i][j] = true;
        bool res = dfs(board, word, visited, i - 1, j, k + 1) ||
                   dfs(board, word, visited, i + 1, j, k + 1) ||
                   dfs(board, word, visited, i, j - 1, k + 1) ||
                   dfs(board, word, visited, i, j + 1, k + 1);
        visited[i][j] = false;
        
        return res;
    }
};

class Solution {
    public boolean exist(char[][] board, String word) {
        if (board == null || board.length == 0 || board[0].length == 0) {
            return false;
        }
        
        int m = board.length;
        int n = board[0].length;
        boolean[][] visited = new boolean[m][n];
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (dfs(board, word, visited, i, j, 0)) {
                    return true;
                }
            }
        }
        
        return false;
    }
    
    private boolean dfs(char[][] board, String word, boolean[][] visited, int i, int j, int k) {
        if (k == word.length()) {
            return true;
        }
        if (i < 0 || i >= board.length || j < 0 || j >= board[0].length || visited[i][j] || board[i][j] != word.charAt(k)) {
            return false;
        }
        
        visited[i][j] = true;
        boolean res = dfs(board, word, visited, i - 1, j, k + 1) ||
                      dfs(board, word, visited, i + 1, j, k + 1) ||
                      dfs(board, word, visited, i, j - 1, k + 1) ||
                      dfs(board, word, visited, i, j + 1, k + 1);
        visited[i][j] = false;
        
        return res;
    }
}

func exist(board [][]byte, word string) bool {
    if len(board) == 0 || len(board[0]) == 0 {
        return false
    }
    
    m, n := len(board), len(board[0])
    visited := make([][]bool, m)
    for i := 0; i < m; i++ {
        visited[i] = make([]bool, n)
    }
    
    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            if dfs(board, word, visited, i, j, 0) {
                return true
            }
        }
    }
    
    return false
}

func dfs(board [][]byte, word string, visited [][]bool, i, j, k int) bool {
    if k == len(word) {
        return true
    }
    if i < 0 || i >= len(board) || j < 0 || j >= len(board[0]) || visited[i][j] || board[i][j] != word[k] {
        return false
    }
    
    visited[i][j] = true
    res := dfs(board, word, visited, i-1, j, k+1) ||
           dfs(board, word, visited, i+1, j, k+1) ||
           dfs(board, word, visited, i, j-1, k+1) ||
           dfs(board, word, visited, i, j+1, k+1)
    visited[i][j] = false
    
    return res
}

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        if not board or not board[0]:
            return False
        
        m, n = len(board), len(board[0])
        visited = [[False] * n for _ in range(m)]
        
        for i in range(m):
            for j in range(n):
                if self.dfs(board, word, visited, i, j, 0):
                    return True
        
        return False
    
    def dfs(self, board, word, visited, i, j, k):
        if k == len(word):
            return True
        if i < 0 or i >= len(board) or j < 0 or j >= len(board[0]) or visited[i][j] or board[i][j] != word[k]:
            return False
        
        visited[i][j] = True
        res = self.dfs(board, word, visited, i-1, j, k+1) \
              or self.dfs(board, word, visited, i+1, j, k+1) \
              or self.dfs(board, word, visited, i, j-1, k+1) \
              or self.dfs(board, word, visited, i, j+1, k+1)
        visited[i][j] = False
        
        return res

var exist = function(board, word) {
    if (!board || !board.length || !board[0].length) {
        return false;
    }
    
    const m = board.length;
    const n = board[0].length;
    const visited = Array.from(Array(m), () => new Array(n).fill(false));
    
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (dfs(board, word, visited, i, j, 0)) {
                return true;
            }
        }
    }
    
    return false;
};

const dfs = function(board, word, visited, i, j, k) {
    if (k === word.length) {
        return true;
    }
    if (i < 0 || i >= board.length || j < 0 || j >= board[0].length || visited[i][j] || board[i][j] !== word.charAt(k)) {
        return false;
    }
    
    visited[i][j] = true;
    const res = dfs(board, word, visited, i-1, j, k+1) ||
                dfs(board, word, visited, i+1, j, k+1) ||
                dfs(board, word, visited, i, j-1, k+1) ||
                dfs(board, word, visited, i, j+1, k+1);
    visited[i][j] = false;
    
    return res;
};
取自“https://www.aigetting.com/index.php?title=题目:单词搜索&oldid=2101”