问题
该文章的最新版本已迁移至个人博客【比特飞】，单击链接 https://www.byteflying.com/archives/3937 访问。
给定一个赎金信 (ransom) 字符串和一个杂志(magazine)字符串，判断第一个字符串ransom能不能由第二个字符串magazines里面的字符构成。如果可以构成，返回 true ；否则返回 false。
(题目说明：为了不暴露赎金信字迹，要从杂志上搜索各个需要的字母，组成单词来表达意思。)
注意：你可以假设两个字符串均只含有小写字母。
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
示例
该文章的最新版本已迁移至个人博客【比特飞】，单击链接 https://www.byteflying.com/archives/3937 访问。
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);
Console.ReadKey();
}
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;
}
}以上给出4种算法实现，以下是这个案例的输出结果：
该文章的最新版本已迁移至个人博客【比特飞】，单击链接 https://www.byteflying.com/archives/3937 访问。
True
False
False
True分析：
显而易见，以上4种算法的时间复杂度均为： 