心得

這題要比對字串變數ransomNote是否存在於字串變數magazine裡。

問題

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.

Note:
You may assume that both strings contain only lowercase letters.

canConstruct("a", "b") -> false
canConstruct("aa", "ab") -> false
canConstruct("aa", "aab") -> true

答案

1. 先將所有字母的數量統計在比較

   public class Solution {
       public bool CanConstruct(string ransomNote, string magazine) {
           if (ransomNote.Length > magazine.Length)
           {
               return false;
           }
   
           Dictionary<char, int> dty_1 = getCharCount(ransomNote);
           Dictionary<char, int> dty_2 = getCharCount(magazine);
   
           foreach (var item in dty_1)
           {
               int tmp = 0;
               if (!dty_2.TryGetValue(item.Key, out tmp) || item.Value > tmp)
               {
                   return false;
               }
           }
   
   
           return true;
       }
       
       private Dictionary<char, int> getCharCount(string str)
       {
           Dictionary<char, int> dty = new Dictionary<char, int>();
   
           while (str.Length > 0)
           {
               dty.Add(str[0], str.Count(x => x == str[0]));
               str = str.Replace(str[0].ToString(), "");
           }
   
           return dty;
       }
   }

2. 方法1的簡化版

   public class Solution {
       public bool CanConstruct(string ransomNote, string magazine) {
           if (ransomNote.Length > magazine.Length)
           {
               return false;
           }
   
           while (ransomNote.Length > 0)
           {
               if (ransomNote.Count(x => x == ransomNote[0]) > magazine.Count(x => x == ransomNote[0]))
               {
                   return false;
               }
   
               ransomNote = ransomNote.Replace(ransomNote[0].ToString(), "");
           }
   
           return true;
       }
   }

3. 這方法是在解答內看到的，解題思路與方法1差不多但是速度快了很多。

   public class Solution {
       public bool CanConstruct(string ransomNote, string magazine) {
           if (ransomNote.Length > magazine.Length)
           {
               return false;
           }
       
           int[] table = new int[26];
           foreach (var item in magazine)
           {
               table[item - 'a']++;
           }
           foreach (var item in ransomNote)
           {
               table[item - 'a']--;
               if (table[item - 'a'] < 0)
               {
                   return false;
               }
           }
       
           return true;
       }
   }