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 =

[
  ['o','a','a','n'],
  ['e','t','a','e'],
  ['i','h','k','r'],
  ['i','f','l','v']
]

Return ["eat","oath"].

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

二. 題目分析

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

一種被廣為使用的方法是使用字典樹，網上的相關介紹不少，簡單沿用一種說法，就是一種單詞查找樹，Trie樹，屬於樹形結構，是一種哈希樹的變種。典型應用是用於統計，排序和保存大量的字符串（但不僅限於字符串），所以經常被搜索引擎系統用於文本詞頻統計。它的優點是：利用字符串的公共前綴來減少查詢時間，最大限度地減少無謂的字符串比較，查詢效率比哈希樹高。

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

而具體的解題思路是：

三. 示例代碼

以下代碼雖然使用字典樹來改進dfs，但AC後發現算法還是比較耗時：

#include 
#include 
#include 
#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 findWords(vector>& board, vector& words) 
    {
        const int x = board.size();
        const int y = board[0].size();
        for (auto ptr : words)
            tree.insert(ptr); // 將候選單詞插入字典樹中

        vector result;

        for (int i = 0; i < x; ++i)
        {
            for (int j = 0; j < y; ++j)
            {
                // 用於記錄走過的路徑
                vector > way(x, vector(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 > &board, vector > way, string word, int x, int y, vector &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();
    }
};

以下是網上一種使用字典樹的算法，耗時48ms - 56ms：

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 findWords(vector>& board, vector& words) {
        Trie *trie = new Trie();
        for (auto &s : words)
            trie->insert(s);
        m = board.size();
        n = board[0].size();

        vector 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> &board, vector &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();
    }
};

四. 小結

學習並初次使用了字典樹，並不是十分熟悉，寫出的代碼計算比較耗時。