Blogs Hub

Ransom Note - MiniTV

Ransom Note - मिनी टीवी

Given an arbitrary ransom note string and another string containing letters from all the magazines, write a function that will return true if the ransom note can be constructed from the magazines; otherwise, it will return false.

Each letter in the magazine string can only be used once in your ransom note.

 

Example 1:

Input: ransomNote = "a", magazine = "b"

Output: false

 

Example 2:

Input: ransomNote = "aa", magazine = "ab"

Output: false

 

Example 3:

Input: ransomNote = "aa", magazine = "aab"

Output: true

 

Constraints:

You may assume that both strings contain only lowercase letters.

 

Solution:

using System;
using System.Collections.Generic;
using System.Text;

namespace LeetCode.AskGif.Easy.String
{
    public class CanConstructSoln
    {
        public bool CanConstruct(string ransomNote, string magazine)
        {
            var map = new Dictionary<char, int>();
            for (int i = 0; i < magazine.Length; i++)
            {
                if (map.ContainsKey(magazine[i]))
                {
                    map[magazine[i]]++;
                }
                else
                {
                    map.Add(magazine[i], 1);
                }
            }

            for (int i = 0; i < ransomNote.Length; i++)
            {
                if (!map.ContainsKey(ransomNote[i]))
                {
                    return false;
                }
                else
                {
                    map[ransomNote[i]]--;
                    if (map[ransomNote[i]] == 0)
                    {
                        map.Remove(ransomNote[i]);
                    }
                }
            }

            return true;
        }
    }
}

Time Complexity: O(n)

Space Complexity: O(n)

 

Unit Tests:

using LeetCode.AskGif.Easy.String;
using Microsoft.VisualStudio.TestTools.UnitTesting;
using System;
using System.Collections.Generic;
using System.Text;

namespace CodingUnitTest.Easy.String
{
    [TestClass]
    public class CanConstructSolnTests
    {
        [TestMethod]
        public void CanConstructSoln_First()
        {
            var ransomNote = "a";
            var magazine = "b";
            var output = false;
            var res = new CanConstructSoln().CanConstruct(ransomNote, magazine);

            Assert.AreEqual(res, output);
        }

        [TestMethod]
        public void CanConstructSoln_Second()
        {
            var ransomNote = "aa";
            var magazine = "ab";
            var output = false;
            var res = new CanConstructSoln().CanConstruct(ransomNote, magazine);

            Assert.AreEqual(res, output);
        }

        [TestMethod]
        public void CanConstructSoln_Third()
        {
            var ransomNote = "aa";
            var magazine = "aab";
            var output = true;
            var res = new CanConstructSoln().CanConstruct(ransomNote, magazine);

            Assert.AreEqual(res, output);
        }
    }
}