• + 6 comments

    Here is a solution that actually uses the notion of "Sparse Arrays" (if you used Maps or LINQ you really missed the point of the exercise):

    using System;
    using System.Collections.Generic;
    using System.IO;
    
    class Solution {
        
        public class Node {
            
            private int count = 0;
            private int depth;
            private Node[] subnodes = null;
            
            private Node[] Subnodes { 
                get {
                    if ( subnodes == null ) {
                        subnodes = new Node[52]; // support A-Z a-z
                    }
                    return subnodes;
                }
            }
            
            public Node () : this(0) {}
            
            private Node ( int depth ) {
                this.depth = depth;
            }
            
            public int Add ( string str ) {
                Node current = this;
                for( int i=0; i<str.Length; i++ ) {
                    int index = CharNodeIndex(str[i]);
                    if ( current.Subnodes[index] == null ) {
                        current.Subnodes[index] = new Node( depth + 1 ); 
                    }
                    current = current.Subnodes[index];
                }
                current.count++;
                return current.count;
            }
    
            public int CountOf( string str ) {
                Node current = this;
                for( int i=0; i<str.Length; i++ ) {
                    int index = CharNodeIndex(str[i]);
                    if ( current.Subnodes[index] == null ) {
                        return 0; 
                    }
                    current = current.Subnodes[index];
                }
                return current.count;
            }
    
            private int CharNodeIndex ( char c ) {
                int index = 0;
                if ( c >= 'A' && c <= 'Z' ) {
                    index = c - 'A';
                } else if ( c >= 'a' && c <= 'z' ) {
                    index = c - 'a' + 26;
                } else {
                    throw new ArgumentException("String may only contain the letters A-Z and a-z");
                }
                return index;
            }
            
        }
        
        static void Main(String[] args) {
            Node node = new Node();
            
            int strCount = int.Parse(Console.In.ReadLine());
            for ( int i=0; i<strCount; i++ ) {
                string str = Console.In.ReadLine();
                node.Add( str );
            }
            
            int queryCount = int.Parse(Console.In.ReadLine());
            for ( int i=0; i<queryCount; i++ ) {
                string str = Console.In.ReadLine();
                Console.Out.WriteLine( node.CountOf(str) );
            }
        }
    }