leetcode笔记：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.

    For example,

    Given words =["oath","pea","eat","rain"]and board =

<code class="hljs json">[  ['o','a','a','n'],  ['e','t','a','e'],  ['i','h','k','r'],  ['i','f','l','v']]</code>

    Return["eat","oath"].

    Note:

    You may assume that all inputs are consist of lowercase lettersa-z.

    二. 题目分析

    若沿用Word Search的方法，必定超时，

leetcode笔记：Word Search II

    一种被广为使用的方法是使用字典树，网上的相关介绍不少，简单沿用一种说法，就是一种单词查找树，Trie树，属于树形结构，是一种哈希树的变种。典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希树高。

    其具体性质、查找方法等可参照：http://baike.baidu.com/link?url=BR1qdZ2oa8BIRbgtD6_oVsaBhzRecDJ0MMFntUvPGNjpG3XgJZihyUdFAlw1Pa30-OFUsNJRWPSanHng65l-Ja

    而具体的解题思路是：

    三. 示例代码

    以下代码虽然使用字典树来改进dfs，但AC后发现算法还是比较耗时：

<code class="hljs cpp">#include<iostream>#include<vector>#include<string>#include using namespace std;class TrieNode{public:    TrieNode() // 构造函数    {        for (int i = 0; i < 26; ++i)            next[i] = NULL;        end = false;    }    void insert(string s)    {        if (s.empty())        {            end = true;            return;        }        if (next[s[0] - 'a'] == NULL)            next[s[0] - 'a'] = new TrieNode();        next[s[0] - 'a']->insert(s.substr(1)); // 右移一位截取字符串s，继续递归插入    }    bool search(string key)    {        if (key.empty())            return end;        if (next[key[0] - 'a'] == NULL)            return false;        return next[key[0] - 'a']->search(key.substr(1));    }    bool startsWith(string prefix)    {        if (prefix.empty())            return true;        if (next[prefix[0] - 'a'] == NULL)            return false;        return next[prefix[0] - 'a']->startsWith(prefix.substr(1));    }private:    TrieNode *next[26];    bool end;};class Tri{public:    Tri(){        root = new TrieNode();    }    void insert(string s)    {        root->insert(s); // 调用TrieNode类的方法    }    bool search(string k)    {        return root->search(k);    }    bool startsWith(string p)    {        return root->startsWith(p);    }private:    TrieNode *root;};class Solution{public:    vector<string>findWords(vector<vector<char>>& board, vector<string>& words)     {        const int x = board.size();        const int y = board[0].size();        for (auto ptr : words)            tree.insert(ptr); // 将候选单词插入字典树中        vector<string>result;        for (int i = 0; i < x; ++i)        {            for (int j = 0; j < y; ++j)            {                // 用于记录走过的路径                vector<vector<b>> way(x, vector<b>(y, false));                dfs(board, way, "", i, j, result);            }        }        // 以下操作排除重复出现的单词        sort(result.begin(), result.end());        result.erase(unique(result.begin(), result.end()), result.end());        return result;    }private:    Tri tree;    void dfs(vector<vector<char>> &board, vector<vector<b>> way, string word, int x, int y, vector<string>&result)    {        if (x < 0 || x >= board.size() || y < 0 || y >= board[0].size()) // 超出边界            return;        if (way[x][y])            return;        word.push_back(board[x][y]);        if (tree.search(word))            result.push_back(word);        if (tree.startsWith(word))        {            way[x][y] = true;            dfs(board, way, word, x + 1, y, result);            dfs(board, way, word, x - 1, y, result);            dfs(board, way, word, x, y + 1, result);            dfs(board, way, word, x, y - 1, result);            way[x][y] = false;        }        word.pop_back();    }};</string></vector<b></vector<char></bool></vector<b></string></string></vector<char></string></string></vector></iostream></code>

    以下是网上一种使用字典树的算法，耗时48ms - 56ms：

<code class="hljs cpp">class Trie {    public:    Trie *next[26];    bool exist;    Trie() {        fill_n(next, 26, nullptr);        exist = false;    }    ~Trie() {        for (int i = 0; i < 26; ++i)            delete next[i];    }    void insert(const string &t) {        Trie *iter = this;        for (int i = 0; i < t.size(); ++i) {            if (iter->next[t[i] - 'a'] == nullptr)                iter->next[t[i] - 'a'] = new Trie();            iter = iter->next[t[i] - 'a'];        }        iter->exist = true;    }};class Solution {    public:    int m, n;    vector<string>findWords(vector<vector<char>>& board, vector<string>& words) {        Trie *trie = new Trie();        for (auto &s : words)            trie->insert(s);        m = board.size();        n = board[0].size();        vector<string>ret;        string sofar;        for (int i = 0; i < m; ++i) {            for (int j = 0; j < n; ++j) {                bc(board, ret, sofar, trie, i, j);            }        }        return ret;    }    void bc(vector<vector<char>> &board, vector<string>&ret, string &sofar, Trie *root, int x, int y) {        if (x < 0 || y < 0 || x >= m || y >= n || board[x][y] == '\0' || root == nullptr)            return ;        if (root->next[board[x][y] - 'a'] == nullptr)            return ;        root = root->next[board[x][y] - 'a'];        char t = '\0';        swap(t, board[x][y]);        sofar.push_back(t);        if (root->exist) {            root->exist = false;            ret.push_back(sofar);        }        bc(board, ret, sofar, root, x, y + 1);        bc(board, ret, sofar, root, x + 1, y);        bc(board, ret, sofar, root, x - 1, y);        bc(board, ret, sofar, root, x, y - 1);        swap(t, board[x][y]);        sofar.pop_back();    }};</string></vector<char></string></string></vector<char></string></code>

    四. 小结

    学习并初次使用了字典树，并不是十分熟悉，写出的代码计算比较耗时，

电脑资料