• + 0 comments

    I used your solution to help me with my generic one but using LinkedLists instead of fixed size arrays

    using System;
    using System.Collections.Generic;
    using System.IO;
    class Solution {
        static void Main(String[] args) {
            int numStrings = Int32.Parse(Console.ReadLine());
    
            var strings = new SparseArray<string, char>();
    
            for(int i = 0; i < numStrings; i++)
                strings.Add(Console.ReadLine());
    
            int numQueries = Int32.Parse(Console.ReadLine());
    
            for(int i = 0; i < numQueries; i++)
            {
                string query = Console.ReadLine();
                Console.WriteLine(strings.Count(query));
            }
        }
    }
    
    class SparseArrayNode<T>
    {
        private T _item;
        private LinkedList<SparseArrayNode<T>> _list = new LinkedList<SparseArrayNode<T>>();
    
        public int Count { get; set; } = 0;
    
        public SparseArrayNode() { }
    
        public SparseArrayNode(T item)
        {
            _item = item;
        }
    
        public SparseArrayNode<T> AddChild(T item)
        {
            var sparseArrayNode = _list.AddLast(new SparseArrayNode<T>(item));
            return sparseArrayNode.Value;
        }
    
        public SparseArrayNode<T> Find(T item)
        {
            var currentNode = _list.First;
    
            while(currentNode != null)
            {
                if(currentNode.Value._item.Equals(item))
                    return currentNode.Value;
    
                currentNode = currentNode.Next;
            }
    
            return null;
        }
    }
    
    class SparseArray<TCollection, TItem> where TCollection : IEnumerable<TItem>
    {
        SparseArrayNode<TItem> _root = new SparseArrayNode<TItem>();
    
        public void Add(TCollection value)
        {
            var current = _root;
    
            foreach(var item in value)
            {
                var node = current.Find(item);
    
                if(node == null)
                    node = current.AddChild(item);
    
                current = node;
            }
    
            current.Count++;
        }
    
        public SparseArrayNode<TItem> Find(TCollection value)
        {
            var current = _root;
    
            foreach(var item in value)
            {
                current = current.Find(item);
    
                if(current == null)
                    break;
            }
    
            return current;
        }
    
        public int Count(TCollection value)
        {
            var node = Find(value);
            return node != null ? node.Count : 0;
        }
    }