https://www.hackerrank.com/challenges/password-cracker/problem

PasswordCracker.cs

using System;
using System.Collections.Generic;
using System.Linq;

namespace PasswordCracker
{
    public class TrieNode
    {
        public IDictionary<char, TrieNode> keys;
        public bool end;
    }
    class Program
    {
        static TrieNode RootTrie;
        static void Main(string[] args)
        {
            var n = int.Parse(Console.ReadLine());
            while(n-->0)
            {
                var x = Console.ReadLine();
                var passwords = Console.ReadLine().Split(' ');
                var pwd = Console.ReadLine();
                RootTrie = CreateTrie(passwords);
                var res = new List<string>();
                if(CheckPassword(RootTrie, pwd, 0, 0, res))
                {
                    Console.WriteLine(string.Join(" ", res.ToArray()));
                }
                else 
                {
                    Console.WriteLine("WRONG PASSWORD");
                }
            }

            Console.ReadKey();
        }

        static TrieNode CreateTrie(string[] pwds)
        {
            var trie = new TrieNode() { keys = new Dictionary<char, TrieNode>()};
            foreach (var p in pwds)
            {
                var t = trie;
                for (int i = 0; i < p.Length; i++)
                {
                    if(!t.keys.ContainsKey(p[i]))
                    {
                        t.keys.Add(p[i], new TrieNode() { keys = new Dictionary<char, TrieNode>()});
                        t.end = t.end || i == p.Length - 1;
                    }

                    t = t.keys[p[i]];
                }
            }
            return trie;
        }

        static bool CheckPassword(TrieNode trie, string pwd, int s, int i, List<string> res)
        {
            if(i == pwd.Length)
            {
                return true;
            }

            if(i >= pwd.Length || !trie.keys.ContainsKey(pwd[i]))
            {
                if(res.Any()) res.RemoveAt(res.Count - 1);
                return false;
            }

            if(trie.end) 
            {
                res.Add(pwd.Substring(s,i-s+1));
                var top = CheckPassword(RootTrie, pwd, i + 1, i+1, res);
                if(!top)
                {
                    return CheckPassword(trie.keys[pwd[i]], pwd, s, i + 1, res);
                }
                return true;
            }
            return CheckPassword(trie.keys[pwd[i]], pwd, s, i + 1, res);
        }
    }
}