Implement a trie (prefix tree) for string matching?

public class TrieNode {

public TrieNode[] Children = new TrieNode[26];

public bool IsEnd = false;

public class Trie {

private TrieNode root;

public Trie() {

root = new TrieNode();

public void Insert(string word) {

TrieNode node = root;

foreach (char c in word) {

int idx = c - 'a';

if (node.Children[idx] == null)

node.Children[idx] = new TrieNode();

node = node.Children[idx];

node.IsEnd = true;

public bool Search(string word) {

TrieNode node = SearchNode(word);

return node != null && node.IsEnd;

public bool StartsWith(string prefix) {

return SearchNode(prefix) != null;

private TrieNode SearchNode(string word) {

TrieNode node = root;

foreach (char c in word) {

int idx = c - 'a';

if (node.Children[idx] == null) return null;

Follow on:

node = node.Children[idx];

return node;

Explanation:

Standard trie with insert, search, and prefix checking.