Trie data structure: 425 Word square

 Here is the gist. 

Ideally it should take me less than 10 minutes to come out Trie data structure with design, and then go over depth first search, word by word, each word should consider if the first few chars ( 0 - level - 1) should be fixed, which can be looked up in ith column, i's value is level. 

When I worked on my first practice yesterday, I did not come out the clear idea illustrated in the following graph. It should be really simple and straightforward. 

	using System;
	using System.Collections.Generic;
	using System.Linq;
	using System.Text;
	using System.Threading.Tasks;
	namespace _435_word_square
	{
	class Program
	{
	static void Main(string[] args)
	{
	var list = new List<string>() { "abat", "baba", "atan", "atal" };
	var result = WordSquares(list);
	}
	public class Trie
	{
	public List<int> Indexes;
	public Trie[] Children;
	public Trie()
	{
	Children = new Trie[26];
	Indexes = new List<int>();
	}
	/// <summary>
	///
	/// </summary>
	/// <param name="words"></param>
	/// <returns></returns>
	public Trie BuildTrie(List<string> words)
	{
	var root = new Trie();
	for (int i = 0; i < words.Count; i++)
	{
	var start = root;
	var word = words[i];
	for(int j = 0; j < word.Count(); j++)
	{
	var next = word[j] - 'a';
	if (start.Children[next] == null)
	{
	start.Children[next] = new Trie();
	}
	start = start.Children[next];
	start.Indexes.Add(i);
	}
	}
	return root;
	}
	}
	/// <summary>
	///
	/// </summary>
	/// <param name="words"></param>
	/// <returns></returns>
	public static List<List<string>> WordSquares(List<string> words)
	{
	var trie = new Trie();
	var root = trie.BuildTrie(words);
	var length = words[0].Length;
	var output = new string[length];
	var result = new List<List<string>>();
	foreach (var word in words)
	{
	output[0] = word;
	runDFS(words, 1, root, output, result);
	}
	return result;
	}
	/// <summary>
	///
	/// </summary>
	/// <param name="words"></param>
	/// <param name="level"></param>
	/// <param name="root"></param>
	/// <param name="output"></param>
	/// <param name="result"></param>
	private static void runDFS(List<string> words, int level, Trie root, string[] output, List<List<string>> result)
	{
	if (level >= words[0].Count())
	{
	result.Add(new List<string>(output));
	return;
	}
	// baba
	// a
	// b
	// a
	// The idea is that ith column should be same as ith row for i = 0 to 3
	var prefix = "";
	for (int i = 0; i < level; i++)
	{ // level - index
	prefix += output[i][level].ToString(); // find "a" - level 1
	}
	var start = root;
	for(int i = 0; i < prefix.Length;i++)
	{
	var next = prefix[i] - 'a';
	if (start.Children[next] == null)
	{
	return;
	}
	start = start.Children[next];
	}
	foreach (var item in start.Indexes)
	{
	output[level] = words[item];
	runDFS( words, level + 1, root, output, result);
	}
	}
	}
	}

view raw 425WordSquare.cs hosted with ❤ by GitHub

Here are some highlights: