Leetcode (212) Word Search II

9418 ワード

lettecode 検索

タイトル:
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”].

題意:いくつかの単語を指定し、1つのboard上で単語テーブル内のすべての単語を見つけるように要求します.

考え方:単語を探すには、基本的には各位置を起点として列挙し、起点から深さ優先検索を行い、すべての単語を見つけることであるが、このような時間複雑度は指数級であり、枝を切る必要がある.枝切りの考え方も簡単で、暴力的な列挙の場合、exampleのように「athflv」があるかもしれませんが、実際には単語表にaで始まる単語はないので、aで始まるすべての検索は必要なく、枝切りの効果を達成します.特定の操作では、単語テーブルに辞書ツリーを作成し、単語テーブルにない単語を枝切りしてチェックできます.辞書の複雑度はO(m)であり,mは辞書中の単語の最長長である.従って,全時間複雑度はO(n 3 m)にはるかに及ばず,すなわち緩やかな上界である.

コード:

class Solution {
public:
    vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
        root = new TrieNode();
        vector<string> ans;
        for (auto word: words)
        {
            insert(word);
        }

        int rows=board.size();
        if (rows == 0) return ans;
        int cols=board[0].size();

        for (int i=0;ifor (int j=0;jif (root->next[board[i][j]-'a'])
                {
                    string word=string(1, board[i][j]);
                    if (isWord(word)) ans.push_back(word);

                    vis[i][j]=true;
                    dfs(i, j, board, ans, word);
                    vis[i][j]=false;
                }
            }
        }

        sort(ans.begin(), ans.end());
        auto last = unique(ans.begin(), ans.end());
        return vector<string>(ans.begin(), last);
    }
private:
    static const int dir[][2];
    bool vis[100][100];
    void dfs(int x, int y, const vector<vector<char>>& board, vector<string>& ans, const string& word)
    {
        int rows=board.size(), cols=board[0].size();
        for (int i=0;i<4;++i)
        {
            int nx=x+dir[i][0], ny=y+dir[i][1];
            if (nx<0 || ny<0 || nx>=rows || ny>=cols || vis[nx][ny]) continue;

            string newWord = word+board[nx][ny];
            if (hasPath(newWord))
            {
                if (isWord(newWord))
                {
                    ans.push_back(newWord);
                }
                vis[nx][ny]=true;
                dfs(nx, ny, board, ans, newWord);
                vis[nx][ny]=false;
            }
        }
    }


    struct TrieNode 
    {
        bool isEnd;
        TrieNode* next[26];
        TrieNode(bool is=false)
        {
            isEnd = is;
            memset(next, 0, sizeof(next));
        }
    };

    TrieNode* root;

    void free(TrieNode* node)
    {
        if (!node) return;
        for (int i=0;i<26;++i)
        {
            free(node->next[i]);
        }
    }

    void insert(const string& word)
    {
        TrieNode* node=root;
        for (int i=0;iint idx = word[i]-'a';
            if (!node->next[idx])
            {
                node->next[idx] = new TrieNode();
            }
            node = node->next[idx];
            if (i == word.length()-1) node->isEnd=true;
        }
    }

    bool hasPath(const string& word)
    {
        TrieNode* node=root;
        for (int i=0;iint idx = word[i]-'a';
            if (node->next[idx])
            {
                node = node->next[idx];
            }
            else
            {
                return false;
            }
        }
        return true;
    }

    bool isWord(const string& word)
    {
        TrieNode* node=root;
        for (int i=0;iint idx = word[i]-'a';
            if (node->next[idx])
            {
                node = node->next[idx];
            }
            else
            {
                return false;
            }
        }
        return node->isEnd;
    }
};

const int Solution::dir[][2] ={1,0,0,1,-1,0,0,-1};

[leetcode] CompareVersionNumbers

jspページタイミングリフレッシュの方法