# 212. Word Search II

題目：<https://leetcode.com/problems/word-search-ii/>

解法：backtracking，並藉由字典樹當作剪枝條件跟終止條件，還可以記錄結果。

Python3：

class Trie:
    def __init__(self):
        self.children = dict()
        self.isWord = False
        self.word = ''

    def insert(self, word: str) -> None:
        cur = self
        for c in word:
            if c not in cur.children:
                cur.children[c] = Trie()
            cur = cur.children[c]
        cur.isWord = True
        cur.word = word

    def search(self, word: str) -> bool:
        cur = self
        for c in word:
            if c not in cur.children:
                return False
            cur = cur.children[c]
        return cur.isWord

class Solution:
    def findWords(self, board: list[list[str]], words: list[str]) -> list[str]:
        def backtrack(x, y, trie):
            if trie.isWord:
                output.add(trie.word)
            visited.add((x, y))
            if x > 0 and (x-1, y) not in visited and board[x-1][y] in trie.children:
                backtrack(x-1, y, trie.children[board[x-1][y]])
            if x < m - 1 and (x+1, y) not in visited and board[x+1][y] in trie.children:
                backtrack(x+1, y, trie.children[board[x+1][y]])
            if y > 0 and (x, y-1) not in visited and board[x][y-1] in trie.children:
                backtrack(x, y-1, trie.children[board[x][y-1]])
            if y < n - 1 and (x, y+1) not in visited and board[x][y+1] in trie.children:
                backtrack(x, y+1, trie.children[board[x][y+1]])
            visited.remove((x, y))
            return
        trie = Trie()
        for word in words:
            trie.insert(word)
        m = len(board)
        n = len(board[0])
        visited = set()
        output = set()
        for x in range(m):
            for y in range(n):
                if board[x][y] in trie.children:
                    backtrack(x, y, trie.children[board[x][y]])
        return list(output)

if __name__ == '__main__':
    # board = [["o", "a", "a", "n"], ["e", "t", "a", "e"], ["i", "h", "k", "r"], ["i", "f", "l", "v"]]
    # words = ["oath", "pea", "eat", "rain"]
    
    board = [["o","a","b","n"],["o","t","a","e"],["a","h","k","r"],["a","f","l","v"]]
    words = ["oa","oaa"]

    ans = Solution().findWords(board, words)
    print(ans)

C：

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>

typedef struct Trie{
    struct Trie* children[26];
    bool isWord;
    char* word;
    bool isFind;
} Trie;

Trie* trieCreate() {
    Trie* obj = (Trie*)malloc(sizeof(Trie));
    for (int i = 0; i < 26; i++)
        obj->children[i] = NULL;
    obj->isWord = false;
    obj->isFind = false;
    return obj;
}

void trieInsert(Trie* obj, char * word) {
    Trie* cur = obj;
    for (int i = 0; i < strlen(word); i++) {
        int idx = word[i]-'a';
        if (cur->children[idx] == NULL)
            cur->children[idx] = trieCreate();
        cur = cur->children[idx];
    }
    cur->isWord = true;
    cur->word = word;
}

void trieFree(Trie* obj) {
    for (int i = 0; i < 26; i++)
        if (obj->children[i] != NULL)
            trieFree(obj->children[i]);
    free(obj);
}

char ** findWords(char** board, int boardSize, int* boardColSize, char ** words, int wordsSize, int* returnSize){
    int m = boardSize, n = boardColSize[0];
    int visited[12][12] = {};
    
    void backtrack(int x, int y, Trie* trie) {
        if (trie->isWord)
            trie->isFind = true;
        visited[x][y] = 1;
        if (x > 0 && visited[x-1][y] == 0) {
            int idx = board[x-1][y]-'a';
            if (trie->children[idx] != NULL)
                backtrack(x-1, y, trie->children[idx]);
        }
        if (x < m - 1 && visited[x+1][y] == 0) {
            int idx = board[x+1][y]-'a';
            if (trie->children[idx] != NULL)
                backtrack(x+1, y, trie->children[idx]);
        }
        if (y > 0 && visited[x][y-1] == 0) {
            int idx = board[x][y-1]-'a';
            if (trie->children[idx] != NULL)
                backtrack(x, y-1, trie->children[idx]);
        }
        if (y < n - 1 && visited[x][y+1] == 0) {
            int idx = board[x][y+1]-'a';
            if (trie->children[idx] != NULL)
                backtrack(x, y+1, trie->children[idx]);
        }
        visited[x][y] = 0;
        return;
    }
    
    Trie* trie = trieCreate();
    for (int i = 0; i < wordsSize; i++)
        trieInsert(trie, words[i]);
    for (int x = 0; x < boardSize; x++)
        for (int y = 0; y < boardColSize[x]; y++) {
            int idx = board[x][y]-'a';
            if (trie->children[idx] != NULL)
                backtrack(x, y, trie->children[idx]);
        }
    char ** output = (char**)malloc(sizeof(char*) * wordsSize);
    *returnSize = 0;
    
    void dfs(Trie* trie) {
        if (trie->isFind) {
            output[(*returnSize)++] = trie->word;
        }
        for (int i = 0; i < 26; i++)
            if (trie->children[i] != NULL) {
                dfs(trie->children[i]);
            }
    }
    
    dfs(trie);
    trieFree(trie);
    return output;
}

int main()
{
    int boardSize = 4;
    int * boardColSize = (int*)malloc(sizeof(int) * boardSize);
    char ** board = (char**)malloc(sizeof(char*) * boardSize);
    for (int i = 0; i < boardSize; i++) {
        boardColSize[i] = 4;
        board[i] = (char*)malloc(sizeof(char) * boardColSize[i]);
    }
    board[0][0] = 'o'; board[0][1] = 'a'; board[0][2] = 'b'; board[0][3] = 'n';
    board[1][0] = 'o'; board[1][1] = 't'; board[1][2] = 'a'; board[1][3] = 'e';
    board[2][0] = 'a'; board[2][1] = 'h'; board[2][2] = 'k'; board[2][3] = 'r';
    board[3][0] = 'a'; board[3][1] = 'f'; board[3][2] = 'l'; board[3][3] = 'v';
    char *words[] = {"oa", "oaa"};
    int wordsSize = sizeof(words) / sizeof(words[0]);
    
    int returnSize;
    char ** ans = findWords(board, boardSize, boardColSize, words, wordsSize, &returnSize);
    printf("%d\n", returnSize);
    for (int i = 0; i < returnSize; i++)
        printf("%s\n", ans[i]);
    return 0;
}

###### tags: `leetcode` `string` `trie` `backtracking`