Loading...
墨滴

Briidge

2021/09/13  阅读:26  主题:默认主题

LeetCode 212.单词搜索II

LeetCode 212.单词搜索II(Trie/字典树/前缀树)

输入:board = [["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]], words = ["oath","pea","eat","rain"]
输出:["eat","oath"]

  • 与LeetCode 79.单词搜索I 的区别是 只需要搜索一个单词 (返回 TrueFalse ),而 II 给出的是单词列表(返回所有words中的能搜索到的单词数组)

1.尝试回溯暴搜(超时)

words 中的每个单词,在给出的表格中进行回溯(就像在 单词搜索I 中一样),若找到立即返回

一些注意点:

  • 防止对表格中的字母重复访问的操作可以
    1. 对已访问过的字母设置为特殊字符 board[i][j] = '#',但是后续仍然会有问题!
    2. 设置一个跟board一模一样大小的 visited (布尔类型)数组再进行判断
  • 写的时候恶心,甚至用上 goto 语句
class Solution {
public:
    vector<vector<int>> dir;
    vector<string> res;
    bool dfs(vector<vector<char>>& board, string& word, int row, int col, int length) {
        if (length == word.size()) {
            res.push_back(word);
            return true;
        }
        bool flag = false;
        for (int i = 0; i < 4; i++) {
            if (isValid(row + dir[i][0], col + dir[i][1], board.size(), board[0].size())) {
                if (board[row + dir[i][0]][col + dir[i][1]] == word[length]) {
                    board[row + dir[i][0]][col + dir[i][1]] = '1';
                    if (dfs(board, word, row + dir[i][0], col + dir[i][1], length + 1))
                        flag = true;
                    board[row + dir[i][0]][col + dir[i][1]] = word[length];
                    if (flag)
                        return true;
                }
            }
        }
        return false;
    }
    bool isValid(int i, int j, int m, int n) {
        return i >= 0 && i < m && j >= 0 && j < n;
    }
    vector<stringfindWords(vector<vector<char>>& board, vector<string>& words) {
        dir = {{-10}, {01}, {10}, {0-1}};
        for (int k = 0; k < words.size(); k++) {
            bool flag = false;
            for (int i = 0; i < board.size(); i++) {
                for (int j = 0; j < board[0].size(); j++) {
                    if (board[i][j] == words[k][0]) {
                        board[i][j] = '1';
                        if (dfs(board, words[k], i, j, 1))
                            flag = true;
                        board[i][j] = words[k][0];
                    }
                    if (flag)
                        goto end;
                }
            }
            end:;
        }
        return res;
    }
};

超时输入:类似 ["abababaa","abababab","abababac","abababae"~~~~"abababaz"]


2.字典树(未优化)(超时)

class Trie() {//字典树的一个实现类,貌似节点有好多种形式....
 bool isEnd;
    Trie* next[26];
    
    Trie() {//构造函数初始化
        isEnd = false;
        for (int i = 0; i < 26; i++)
            next[i] = nullptr;
    }
    void insert(string word) {//将字符串word写入字典树
        Trie* node = this;
        for (char ch : word) {
            if (node->next[ch - 'a'] == nullptr) {
                node->next[ch - 'a'] = new Trie();
            }
            node = node->next[ch - 'a'];
        }
        node->isEnd = true;
    }
    bool startsWith(string word)//判断word是否是字典树中某个单词的前缀
    
{
        Trie *node = this;
        for (char each : word)
        {
            if (!node->nxt[each - 'a'])
                return false;
            node = node->nxt[each - 'a'];
        }
        return true;
    }
    bool searchWord(string word)//判断字典树中是否写入过字符串word
    
{
        Trie *node = this;
        for (char each : word)
        {
            if (!node->nxt[each - 'a'])
            {
                return false;
            }
            node = node->nxt[each - 'a'];
        }
        return node->isEnd;
    }
}

字典树解法的大概思路

  • 创建一个字典树,将所有 words 数组中的单词写入

  • 回溯整个表格(仅需一次)

  • 如果当前路径所构成的单词无法在字典树中找到(怎么算无法找到?在字典树中,当前字符串不是某个单词的前缀,即 !startsWith(str);或者找到了目标单词,但该节点的 isEnd == false),回退尝试其他路径;否则如果找到字典树中的某个单词,该单词加入结果中,但是!不能立即返回!!!

具体代码

class Solution
{

public:
    int dir[4][2] = {{-10}, {01}, {10}, {0-1}};//回溯的四个方向
    vector<string> res;
    void dfs(Trie* trie, vector<vector<char>> &board, int row, int col, string s) {
        if (trie->searchWord(s)) {
            res.push_back(s);
        }
        //坐标越界 或 字典树中没有以当前字符串为前缀的单词
        if (row < 0 || row >= board.size() || col < 0 || col >= board[0].size())
            return ;
        if (s.size() > 0 && !trie->startsWith(s))
            return ;
        if (board[row][col] == '#')
            return ;
        char temp = board[row][col];
        board[row][col] = '#';
        for (auto d : dir) {
            dfs(trie, board, row + d[0], col + d[1], s + temp);
        }
        board[row][col] = temp;
    }
    vector<stringfindWords(vector<vector<char>> &board, vector<string> &words) {
        Trie* trie = new Trie();
        for (auto e : words)
            trie->insert(e);
        for (int i = 0; i < board.size(); i++) {
            for (int j = 0; j < board[0].size(); j++) {
                dfs(trie, board, i, j, "");
            }
        }
        return res;
    }
};

与解法一的回溯暴搜相比

  • 解法一需要对每个给出的单词进行全局的搜索,第一个、第二个、第三个...每个单词都要从表格的(0,0)开始回溯搜索;而用字典树只需要对表格回溯一次

对于字典树(Trie树,发音类似try),可以看作一种 二叉树 的扩展,二叉树有 2 个指向子节点的指针;而字典树的每个节点指向其他节点的指针个数 n 等于字符集的个数(通过映射的方式隐含当前字母),比如26个英文字母的字典树 next[0] 可表示字母 a,next[1] 可表示字母 b,以此类推....


对递归回溯的一些思考

  1. 对于当前这层递归回溯的所有可选状态来说,有两种操作方式
    • 先判断可行性,再进入下一层递归。(对所有可选项选择之前判断,不行的话跳到下一个选项;可行的话再进入下一层。可能空间时间会用的少一点,代码太丑陋,而且有时候该函数入口也要进行一个判断)
    • 先进入下一层递归,再判断可行性。(不管这个选项的可行性,直接进入下一层递归,在递归函数的开头再进行判断,不行的话再返回。与上一个操作相比,只需要在函数开头增加几个判断,函数入口也可以直接进入)

Briidge

2021/09/13  阅读:26  主题:默认主题

作者介绍

Briidge