LeetCode 单词搜索

题目描述：

image.png image.png

解题思路：
这里考虑到使用字符串，并且设计到字符的搜索，想到采用前缀树来进行存储，并根据前缀树进行搜索

1. 建立前缀树的数据结构
2. 遍历字符数组，进行搜索
3. 搜索过的字符进行标记防止重复搜索
4. 搜索到之后去重，最后返回结果

class TrieNode{
    //前缀树
    TrieNode[] nodes;
    String word;
    public TrieNode(){
        nodes = new TrieNode[26];
        word = "";
    }
}

class Trie{
    public TrieNode root;
    public Trie(){
        root = new TrieNode();
    }
    
    public void insert(String word){
        TrieNode node = root;
        for(char c : word.toCharArray()){
            if(node.nodes[c-'a']==null){
                node.nodes[c-'a'] = new TrieNode();
            }
            node = node.nodes[c-'a'];
        }
        node.word = word;
    }
}

class Solution {
    public static void dfs(int i,int j,char[][]board,TrieNode node,List<String> result){
        if(board[i][j] == '#')
            return;//当前位置已经遍历过了
        char c = board[i][j];
        board[i][j] = '#';//标记当前位置
        if(node.nodes[c-'a']==null){
            board[i][j] = c;
            return;
        }else{
            node = node.nodes[c-'a'];
            if(node.word.length()!=0){
              //去重
                if(!result.contains(node.word)){
                    result.add(node.word);
                }
            }
            
            
            if(i > 0){
                dfs(i-1,j,board,node,result);
            }
            if(i < board.length-1){
                dfs(i+1,j,board,node,result);
            }
            if(j > 0){
                dfs(i,j-1,board,node,result);
            }
            if(j < board[0].length-1){
                dfs(i,j+1,board,node,result);
            }
            board[i][j] = c;
        }
        
    }    
    public List<String> findWords(char[][] board, String[] words) {
        
        if(board.length <= 0 || board[0].length<=0||words.length<=0){
            return new ArrayList<>();
        }
        Trie tree = new Trie();
        for(String s : words){
            tree.insert(s);//通过字典创建前缀树
        }
        
        int row = board.length;
        int column = board[0].length;
        List<String> result = new ArrayList<>();
        for(int i = 0;i<row;i++){
            for(int j = 0; j < column;j++){
                dfs(i,j,board,tree.root,result);
            }
        }
        return result;
        
    }
}