We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Data Structures
  3. Arrays
  4. Sparse Arrays
  5. Discussions

Sparse Arrays

  • azeyad
     + 0 comments

    I tried to find a way to implement a fix that somehow relates to the "Sparse Array" concept, but in sparse array we convert the array into a linked a list with the non empty entries only to save storage, so I imagined that converting the sparse array of word characters to a linked list is the way to go, here is my try:

    using System;
using System.Collections.Generic;
using System.IO;
class Solution {
    static void Main(String[] args) {
        /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution */
        int strCount = int.Parse(Console.In.ReadLine());
        for (int i = 0; i < strCount; i++)
        {
            string str = Console.In.ReadLine();
            AddWord(str);
        }
        int queryCount = int.Parse(Console.In.ReadLine());
        for (int i = 0; i < queryCount; i++)
        {
            string str = Console.In.ReadLine();
            actual_WordCount(str);
        }        
    }
    static WordNode StartWordNode = null;
    static WordNode LastWordNode = null;
    public static void AddWord(string word)
    {
        //Every new word add new word node             
        if (StartWordNode == null)
            LastWordNode = StartWordNode = new WordNode();
        else
            LastWordNode = LastWordNode.NextWordNode = new WordNode();
        CharacterNode currentCharacter = null;
        for (int i = 0; i < word.Length; i++)
        {
            if (currentCharacter == null)
                currentCharacter = LastWordNode.Character = new CharacterNode();
            else
                currentCharacter = currentCharacter.NextCharacterNode = new CharacterNode();
            currentCharacter.Char = word[i];
            currentCharacter.Position = i;
        }
    }    
    private static void actual_WordCount(string word)
        {
            int count = 0;
            WordNode currentWord = StartWordNode;
            while (currentWord != null)
            {
                CharacterNode currentCharNode = currentWord.Character;
                bool allCharsFound = true;
                for (int i = 0; i < word.Length; i++)
                {
                    if (currentCharNode.Char != word[i] || currentCharNode.Position != i || (i == word.Length - 1 && currentCharNode.NextCharacterNode != null))
                    {
                        allCharsFound = false;
                        break;
                    }
                    currentCharNode = currentCharNode.NextCharacterNode;
                }
                if (allCharsFound)
                    count++;
                currentWord = currentWord.NextWordNode;
            }
            Console.WriteLine(count);
        }
        public static void countWords()
        {
            int strCount = int.Parse(Console.In.ReadLine());
            for (int i = 0; i < strCount; i++)
            {
                string str = Console.In.ReadLine();
                AddWord(str);
            }
            int queryCount = int.Parse(Console.In.ReadLine());
            for (int i = 0; i < queryCount; i++)
            {
                string str = Console.In.ReadLine();
                actual_WordCount(str);
            }
        }    
    
}
public class CharacterNode
{
    public char Char { get; set; }
    public int Position { get; set; }
    public CharacterNode NextCharacterNode { get; set; }
}

public class WordNode
{
    public int WordCount { get; set; }
    public CharacterNode Character { get; set; }
    public WordNode NextWordNode { get; set; }
}