212. Word Search II

FindWords.cs

public class Solution {
  private readonly List<string> _result = new();
  
  public IList<string> FindWords(char[][] board, string[] words) {
    var root = CreateTrie(words);
    FindWords(board, root);
    return _result;
  }
  
  static readonly (int row, int col)[] directions = new (int row, int col)[]{
      (-1, 0),
      (0, 1),
      (1, 0),
      (0, -1)
  };
  
  private void FindWords(char[][] board, TrieNode root){
    var rowSize = board.Length;
    var colSize = board[0].Length;
    for(var row = 0; row < rowSize; row++){
      for(var col = 0; col < colSize; col++){
        if(!root.Children.ContainsKey(board[row][col])) continue;
        Backtracking(row, col, root);
      }
    }

    void Backtracking(int row, int col, TrieNode parent){
      var letter = board[row][col];
      var node = parent.Children[letter];

      if(!string.IsNullOrEmpty(node.Word)){
        _result.Add(node.Word);
        node.Word = string.Empty;
      }
      
      board[row][col] = '.'; // mark current row,col as visited
      
      foreach(var dir in directions){
        var neigRow = row + dir.row;
        var neigCol = col + dir.col;
        if(neigRow  < 0 || neigRow >= rowSize || neigCol < 0 || neigCol >= colSize) continue;
        if(!node.Children.ContainsKey(board[neigRow][neigCol])) continue;
        Backtracking(neigRow, neigCol, node);
      }
      board[row][col] = letter;
      
      if(node.Children.Count == 0) parent.Children.Remove(letter);
    }
  }
  
  TrieNode CreateTrie(string[] words){
    var root = new TrieNode();
    foreach(var word in words){
      var current = root;
      foreach(var c in word.AsSpan()){
        if(!current.Children.ContainsKey(c)) current.Children.Add(c, new());
        current = current.Children[c];
      }
      current.Word = word;      
    }
    return root;
  }

  private class TrieNode{
    public Dictionary<char, TrieNode> Children { get; } = new();
    public string Word { get; set; } = string.Empty;
  }
}
/*
[["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]]
["oath","pea","eat","rain"]
[["a","b"],["c","d"]]
["abcb"]
[["o","a","a","n"],["e","t","a","e"],["t","l","k","r"],["i","f","l","a"]]
["alt", "alk", "aaa", "aaat", "oan"]
[["a","b"],["a","a"]]
["aba","baa","bab","aaab","aaa","aaaa","aaba"]
[["b","b","a","a","b","a"],["b","b","a","b","a","a"],["b","b","b","b","b","b"],["a","a","a","b","a","a"],["a","b","a","a","b","b"]]
["abbbababaa"]
[["a"]]
["a"]
[["a","b"]]
["a","b"]
*/