# [212\. Word Search II](https://leetcode.com/problems/word-search-ii/)

- 矩陣裡找單字，跟 79. Word Search 不一樣的是，這次給予的是一個單字陣列。
- Trie + Backtracking

:::spoiler Solution

class TrieNode {
public:
    TrieNode* child[26];
    string str;
    TrieNode()
    {
        for (int i = 0; i < 26; ++i)
        {
            child[i] = nullptr;
        }
        str = "";
    }
};

class Trie {
public:
    TrieNode* root;
    Trie()
    {
        root = new TrieNode();
    }

    void insert(const string& word)
    {
        TrieNode* node = root;
        for (char w : word)
        {
            if (!node->child[w - 'a'])
            {
                node->child[w - 'a'] = new TrieNode();
            }
            node = node->child[w - 'a'];
        }
        node->str = word;
    }    
};

class Solution {
private:
    vector<string> res;
    
public:
    void backtracking(vector<vector<char>>& board, TrieNode* node, int i, int j)
    {
        if (i < 0 || j < 0 || i >= board.size() || j >= board[0].size() || board[i][j] == '#' || !node->child[board[i][j] - 'a'])
        {
            return;
        }

        node = node->child[board[i][j] - 'a'];
        if (!node->str.empty())
        {
            res.push_back(node->str);
            node->str = "";
        }

        char temp = board[i][j];
        board[i][j] = '#';

        backtracking(board, node, i + 1, j);
        backtracking(board, node, i - 1, j);
        backtracking(board, node, i, j + 1);
        backtracking(board, node, i, j - 1);

        board[i][j] = temp;
    }

    vector<string> findWords(vector<vector<char>>& board, vector<string>& words)
    {
        if (board.empty() || board[0].empty()) return {};
        
        Trie t;
        for (const string& word : words) t.insert(word);
        
        for (int i = 0; i < board.size(); ++i)
        {
            for (int j = 0; j < board[0].size(); ++j)
            {
                backtracking(board, t.root, i, j);
            }
        }
        return res;
    }
};

- 時間複雜度：$O()$
- 空間複雜度：$O()$
:::