@yavinci Very interesting solution of combining a Trie with DFS. I learn't a couple of new things from your solution.
I do have a question about your claim that not using a visited matrix helps you save O(n^2) memory. When you save the char value at before each dfs call, the recursive stack allocates O(n^2) chars, while a boolean visited matrix would require only O(n^2) bools. Therefore, isn't it better to use a boolean visited matrix?