心得

這題要比對字串變數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 2 3

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

答案

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

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

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36

   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的簡化版
   
   C#

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

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

   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差不多但是速度快了很多。
   
   C#

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

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

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