心得
這題要比對字串變數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.
123 canConstruct("a", "b") -> falsecanConstruct("aa", "ab") -> falsecanConstruct("aa", "aab") -> true
答案
- 先將所有字母的數量統計在比較
123456789101112131415161718192021222324252627282930313233343536public 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
的簡化版
1234567891011121314151617181920public 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
差不多但是速度快了很多。
123456789101112131415161718192021222324public 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;}}