LeetCode 题解

积跬步，至千里。

单词搜索 II

分类：LeetCode 标签： 字典树 回溯算法 发布于：2019-10-20 ID：212

题目描述

来源于 https://leetcode-cn.com/

给定一个二维网格 board 和一个字典中的单词列表 words，找出所有同时在二维网格和字典中出现的单词。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母在一个单词中不允许被重复使用。

示例:

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

输出: ["eat","oath"]

说明:
你可以假设所有输入都由小写字母 a-z 组成。

提示:

  • 你需要优化回溯算法以通过更大数据量的测试。你能否早点停止回溯？
  • 如果当前单词不存在于所有单词的前缀中，则可以立即停止回溯。什么样的数据结构可以有效地执行这样的操作？散列表是否可行？为什么？ 前缀树如何？如果你想学习如何实现一个基本的前缀树，请先查看这个问题： 实现Trie（前缀树）。

解法：

把待查询的词加入到字典树种，然后从矩阵的各个位置开始深度优先遍历，去和字典树中的单词进行匹配。

class Trie {
public:
    struct Node;
    struct Node{
        string word;
        Node* next['z'-'a'+1]{nullptr};
    };

    Trie() {
        root = new Node;
    }

    void insert(const string& word) {
        Node* p = root;
        for(char ch : word){
            int index = ch - 'a';
            if(p->next[index] == nullptr){
                p->next[index] = new Node;
            }
            p = p->next[index];
        }
        p->word = word;
    }
    
    ~Trie() noexcept {
        // free memory
        ;
    }

    Node* root;
};

class Solution {
public:
    vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
        if(board.empty() || board[0].empty()) return matched_words;
        n_rows = board.size();
        n_cols = board[0].size();
        this->board_ = &board;

        for(const string &word: words){
            trie.insert(word);
        }

        for(size_t i=0;i<n_rows;i++){
            for(size_t j=0;j<n_cols;j++){
                dfs(i, j, trie.root);
            }
        }
        return matched_words;
    }

    void dfs(int row, int col, typename Trie::Node *node){
        vector<vector<char>>& board = *board_;
        char ch = board[row][col];
        if(ch == '#') return;

        node = node->next[ch - 'a'];
        if(node == nullptr) return;
        
        if(!node->word.empty()){
            matched_words.push_back(::move(node->word));
            node->word.clear();
        }
        
        board[row][col] = '#';

        if(row > 0) dfs(row-1, col, node);
        if(row+1 < n_rows) dfs(row+1, col, node);
        if(col > 0) dfs(row, col-1, node);
        if(col+1 < n_cols) dfs(row, col+1, node);

        board[row][col] = ch;
    }

private:
    vector<string> matched_words;
    vector<vector<char>>* board_;
    Trie trie;
    int n_cols;
    int n_rows;
};