public class Solution {
    public List<String> findWords(char[][] board, String[] words) {
        //insert all words into trie
        //for each cell, depth first search from that cell in all directions checking each growing string against the trie
        //if eventually a word is found (all neighbors dont continue making a valid word in trie), then add that word to soln list
        //if at any added character the string no longer is in trie, stop traversing, just return null 
        Trie trie = new Trie();
        for(int i = 0; i < words.length; i++){
            trie.insert(words[i]);
        }
        
        List<String> validWords = new List<String>();
        
        for(int row = 0; row < boards.length; row++){
            for(int col = 0; col < boards[0].length; col++){
                StringBuilder sb = new StringBuilder();
                String validWord = testCharacterOnBoard(board, row, col, trie, sb, validWords);
            }
        }
    }
    
    public static void testCharacter(char[][] board, int row, int col, Trie trie, StringBuilder sb, List<String> validWords){
        if(row < 0 || col < 0 || row >= board.length || col >= board[0].length){
            return null;
        }
        //test current character in trie
        sb.append(board[row][col]);
        String curStr = sb.toString();
        if(trie.startsWith(curStr)){
            if(trie.search(curStr)){ //TODO figure out how to not duplicate the search
                //there is this prefix, and it is a word
                validWords.add(curStr);
            }
            
            //there is this prefix, but it isn't a word
            //search surrounding characters
            testCharacter(board, row+1, col, trie, sb, validWords); //use static list of validWords, otherwise you pass around a lot of memory
            testCharacter(board, row-1, col, trie, sb, validWords);
            testCharacter(board, row, col+1, trie, sb, validWords);
            testCharacter(board, row, col-1, trie, sb, validWords);
        }
        //no such prefix was found, we're at a nonexistent dead word
        
        
        //remove current character from sb
        if (sb.length() > 0) { 
            sb.setLength(sb.length() - 1);
        }
        
    }
}

public class Trie {
    
    private class TrieNode{
        char val;
        HashMap<Character, TrieNode> children;
        
        public TrieNode(char ch){
            val = ch;
            children = new HashMap<Character, TrieNode>();
        }
        
        public TrieNode addChild(char ch){
            
            if(this.children.containsKey(ch)){
                return this.children.get(ch);
            }else{
                TrieNode child = new TrieNode(ch);
                this.children.put(ch, child);
                return child;
            }
        }
    }
    
    TrieNode root;
    
    /** Initialize your data structure here. */
    public Trie() {
        root = new TrieNode(' ');
    }
    
    /** Inserts a word into the trie. */
    public void insert(String word) {
        char[] chArr = word.toCharArray();
        
        this.insert(chArr, this.root, 0);
    }
    
    public void insert(char[] chArr, TrieNode currNode, int currIndex){
        if(currIndex >= chArr.length){
            return;
        }
        
        TrieNode child = currNode.addChild(chArr[currIndex]);
        currIndex++;
        insert(chArr, child, currIndex);
    }
    
    /** Returns true if the word is in the trie. */
    public boolean search(String word) {
        char[] chArr = word.toCharArray();
        
        return search(chArr, this.root, 0);
    }
    
    public boolean search(char[] chArr, TrieNode currNode, int currIndex){
        if(currIndex >= chArr.length){
            return true;
        }
        
        if(currNode.children.containsKey(chArr[currIndex])){
            TrieNode child = currNode.children.get(chArr[currIndex]);
            currIndex++;
            return search(chArr, child, currIndex);
        }else{
            return false;
        }
    }
    
    /** Returns if there is any word in the trie that starts with the given prefix. */
    public boolean startsWith(String prefix) {
        char[] chArr = prefix.toCharArray();
        
        return search(chArr, this.root, 0);
    }
    
    // public boolean startsWith(char[] chArr, TrieNode child, int currIndex){
    //     if(currIndex)
    // }
}