【HARD】Word Search II

发布于: 2019-03-31 16:29
阅读: 28
评论: 0
喜欢: 0

问题

原题链接:https://leetcode.com/problems/word-search-ii/

Given a 2D board and a list of words from the dictionary, find all words in the board.

Each word must 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 in a word.

Example:

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

Output: ["eat","oath"]

Note:

  • You may assume that all inputs are consist of lowercase letters a-z.

分析过程

  • 输入:二维字母表和需要寻找的字符串列表
  • 输出:能在字母表里找到的字符串列表
  • 思路:回溯法暴搜会超时,必须使用字典树。

解决方法

class Solution {
public:
    
    struct TirTree {
        TirTree *child[26] = {};
        string str = "";
    };
    
    struct Point {
        int y;
        int x;
    };
    
    // 建立字典树
    TirTree *buildTirTree(vector<string>& words) {
        TirTree *root = new TirTree();
        
        for (string word : words) {
            TirTree *tmp = root;
            for (char c : word) {
                int v = c - 'a';
                if (!tmp->child[v]) {
                    tmp->child[v] = new TirTree();
                }
                tmp = tmp->child[v];
            }
            tmp->str = word;
        }
        
        return root;
    }
    
    void search(vector<vector<char>>& board, Point& p, TirTree *root, vector<vector<bool>>& used, vector<string>& res) {
        if (!root->str.empty()) {
            res.push_back(root->str);
            root->str = "";
        }
        // 向四个方向找
        vector<Point> locations = {
            {p.y - 1, p.x},
            {p.y + 1, p.x},
            {p.y, p.x - 1},
            {p.y, p.x + 1}
        };
        used[p.y][p.x] = true;
        for (Point& p : locations) {
            if (p.y < 0 || p.y >= board.size() || p.x < 0 || p.x >= board[0].size()) {
                continue;
            }
            if (used[p.y][p.x]) {
                continue;
            }
            if (!root->child[board[p.y][p.x] - 'a']) {
                continue;
            }
            search(board, p, root->child[board[p.y][p.x] - 'a'], used, res);
        }
        used[p.y][p.x] = false;
    }
    
    vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
        vector<string> res;
        // 记录已经使用过的点
        vector<vector<bool>> used(board.size(), vector<bool>(board[0].size(), false));
        // 建立字典树
        TirTree *root = buildTirTree(words);
        // 遍历字符表每个点进行搜索
        for (int y = 0; y < board.size(); ++y) {
            for (int x = 0; x < board[y].size(); ++x) {
                TirTree *node = root->child[board[y][x] - 'a'];
                if (node) {
                    Point origin = {y, x};
                    search(board, origin, node, used, res);
                }
            }
        }

        return res;
    }
};

Thanks for reading.

All the best wishes for you! 💕