[leetcode] 212. Word Search II解題レポート

タイトルリンク: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.
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 .
考え方:1つの比較的直感的な方法は単語ごとにDFS検索を行うが、このような速度は比較的に遅く、その時間の複雑度が最も悪いとO(m^2*n^2*k)に達する.すなわち、単語ごとに地図の各要素から検索を開始し、単語が十分に長く、毎回完全な地図を検索すれば、時間の複雑度は最も悪い.この方法は大量のデータを完成できないに違いない.これは私の最初の考えです.コードは以下の通りです.

class Solution {
public:
    bool DFS(vector<vector<char>>& board, string str, int index, int x, int y, vector<vector<bool>> flag)
    {
        if(index >= str.size()){ result.push_back(str); return true;}
        if(x < 0 || x >= board.size() || y <0 || y >= board[0].size() || flag[x][y] == true)
            return false;
        flag[x][y] = true;
        if(board[x][y] == str[index])
        {
            if(DFS(board, str, index+1, x+1, y, flag) == true) return true;
            if(DFS(board, str, index+1, x-1, y, flag) == true) return true;
            if(DFS(board, str, index+1, x, y+1, flag) == true) return true;
            if(DFS(board, str, index+1, x, y-1, flag) == true) return true;
        }
        return false;
    }
    
    vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
        if(board.size()==0 || words.size()==0) return {};
        int m = board.size(), n = board[0].size();
        
        for(auto str: words)
        {
            bool f = false;
            for(int i =0; i< m && f==false; i++)
                for(int j =0; j < n && f==false; j++)
                    if(board[i][j] == str[0])
                    {
                        vector<vector<bool>> flag(m, vector<bool>(n, false));
                        if(DFS(board, str, 0, i, j, flag) == true)
                            f = true;
                    }
        }
        return result;
    }
private:
    vector<string> result;
};

もっと良い方法は辞書ツリーTrieを利用して、検索する単語をまず辞書ツリーに追加して、それから地図boardの各要素から検索して、上下左右に検索する時その要素が辞書ツリーの中で見つけることができるならば、引き続き検索して、そしてあるノードを検索する時このノードが1つの単語を構成していることを発見したら、結果セットに単語を追加する.辞書ツリーでこの要素が見つからない場合は、現在のブランチの検索を終了します.
コードは次のとおりです.

class Solution {
public:
    struct Trie
    {
        vector<Trie*> child;
        string str;
        Trie(): child(vector<Trie*>(26, NULL)), str(""){}
    };
    
    void addWord(vector<string>& words)
    {
        for(auto str: words){
            Trie* tem = root;
            for(auto ch: str){
                if(tem->child[ch - 'a'] == NULL) 
                    tem->child[ch - 'a'] = new Trie();
                tem = tem->child[ch - 'a'];
            }
            tem->str = str;
        }
    }
    
    void DFS(vector<vector<char>>& board, int x, int y, Trie* node)
    {
        char ch = board[x][y];
        if(node->child[ch-'a'] == NULL || board[x][y] =='$') return;
        if(node->child[ch-'a']->str.size() > 0)
        {
            result.push_back(node->child[ch-'a']->str);
            node->child[ch-'a']->str = "";
        }
        board[x][y] = '$';
        if(y+1 < board[0].size()) DFS(board, x, y+1, node->child[ch - 'a']);
        if(y-1 >= 0) DFS(board, x, y-1, node->child[ch - 'a']);
        if(x+1 < board.size()) DFS(board, x+1, y, node->child[ch - 'a']);
        if(x-1 >=0) DFS(board, x-1, y, node->child[ch - 'a']);
        board[x][y] = ch;
    }

    vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
        if(board.size()==0 || words.size()==0) return {};
        int m = board.size(), n = board[0].size();
        root = new Trie();
        addWord(words);
        for(int i = 0; i< m; i++)
            for(int j =0; j< n; j++)
                DFS(board, i, j, root);
        return result;
    }
    
private:
    vector<string> result;
    Trie* root;
};

参照:https://leetcode.com/discuss/77851/java-15ms-easiest-solution-100-00%25