题目
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
解析
此题难度不大,主要是考虑如何能在较短的时间内完成,双层循环或者排序后循环都会造成Time limit exceeded。因此可以采用映射的方式来对所出现的字母次数进行统计,这样可以达到O(n)的时间复杂度。
由于C语言中没有类似于python中的dict类型,在之前题目中提到过,实现这种dict可以使用数组映射的方式,dictArr[x - 'a']这种方式。
代码(C语言)
bool canConstruct(char* ransomNote, char* magazine) {
int* countArr = (int*)calloc(26, sizeof(int));
int count = 0;
int ransomSize = (int)strlen(ransomNote);
int magzaineSize = (int)strlen(magazine);
for (int i = 0; i < ransomSize; ++i) {
++countArr[ransomNote[i] - 'a'];
++count;
}
for (int i = 0; i < magzaineSize && count > 0; ++i) {
if (countArr[magazine[i] - 'a'] > 0) {
--countArr[magazine[i] - 'a'];
--count;
}
}
free(countArr);
if (count)
return false;
return true;
}
需要说明的是,strlen()耗时较多,因此如果将其放到循环中,每次循环都要计算其值,耗时较长,这样也会发生超时错误。
另外一点,最后count不为0,即应该return false,而不是单纯的count > 0。此处需要读者思考一下。
网友评论