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);
}
}
}
