You are viewing a single comment's thread. Return to all 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; } }
Sparse Arrays
You are viewing a single comment's thread. Return to all comments →
I used your solution to help me with my generic one but using LinkedLists instead of fixed size arrays