# C#LeetCode刷题之#383-赎金信（Ransom Note）

(题目说明：为了不暴露赎金信字迹，要从杂志上搜索各个需要的字母，组成单词来表达意思。)

canConstruct(“a”, “b”😉 -> false

canConstruct(“aa”, “ab”😉 -> false

canConstruct(“aa”, “aab”😉 -> true

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

```public class Program {

public static void Main(string[] args) {
var ransomNote = "aa";
var magazine = "abdfa";

var res = CanConstruct(ransomNote, magazine);
Console.WriteLine(res);

ransomNote = "aa";
magazine = "bb";

res = CanConstruct2(ransomNote, magazine);
Console.WriteLine(res);

ransomNote = "bjaajgea";
magazine = "affhiiicabhbdchbidghccijjbfj";

res = CanConstruct3(ransomNote, magazine);
Console.WriteLine(res);

ransomNote = "edhi";
magazine = "fhjeddgggbajhidhjchiedhdibgeaecffbbbefiabjdhggihccec";

res = CanConstruct4(ransomNote, magazine);
Console.WriteLine(res);

}

private static bool CanConstruct(string ransomNote, string magazine) {
//LeetCode超出内存限制未AC
var startIndex = -1;
for(var i = 0; i < ransomNote.Length; i++) {
if(magazine.Contains(ransomNote[i])) {
startIndex = magazine.IndexOf(ransomNote[i]);
magazine = magazine.Remove(startIndex, 1);
} else {
return false;
}
}
return true;
}

private static bool CanConstruct2(string ransomNote, string magazine) {
//这个解法没AC，输入 aa bb 在VS下返回false
//但在LeetCode上显示返回 true
//不知道为什么，有看官知道告诉我一下，多谢
//总之这个解可能有问题，各位看官请注意！！！
var i = 0;
var j = 0;
if(ransomNote.Length == 1 && !magazine.Contains(ransomNote))
return false;
while(i < ransomNote.Length) {
var temp = ransomNote[i];
while(j < magazine.Length) {
if(magazine[j] != temp) j++;
else {
i++;
break;
}
}
if(i == ransomNote.Length - 1) return true;
if(j >= magazine.Length) return false;
j++;
}
return true;
}

private static bool CanConstruct3(string ransomNote, string magazine) {
//哈希法
var dic = new Dictionary<char, int>();
foreach(var c in ransomNote) {
if(dic.ContainsKey(c)) {
dic[c]++;
} else {
dic[c] = 1;
}
}
foreach(var c in magazine) {
if(dic.ContainsKey(c)) {
dic[c]--;
if(dic[c] < 0) return false;
if(dic[c] == 0) {
dic.Remove(c);
}
}
}
return dic.Count == 0;
}

private static bool CanConstruct4(string ransomNote, string magazine) {
//用整型数组来统计26个字母
//位置 0 代表字母 a，以此类推
var statistics = new int[26];
foreach(var c in magazine) {
statistics[c - 'a']++;
}
foreach(var c in ransomNote) {
if(--statistics[c - 'a'] < 0) return false;
}
return true;
}

}```

```True
False
False
True```