leetcode-353-Ransom-Note

描述


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.

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

分析


实际上就是验证 ransomNote 是否为 magazine 的子集,如果不用 Python,比较容易想到的方法是用哈希表,先将 magazine 这个字符串做一个映射,key 是字符的 ascii 码,value 是字符的个数,再遍历 ransomNote,遇到对应的字符,则 value 减1,如有<0的情况,则返回 false。

解决方案1(C++)


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
bool canConstruct(string ransomNote, string magazine) {
int map_char_int[26] = {0};
for(int i=0; i < magazine.length(); ++i) {
++map_char_int[magazine[i]-'a'];
}
for(int i=0; i < ransomNote.length(); ++i) {
if((--map_char_int[ransomNote[i]-'a']) < 0) {
return false;
}
}
return true;
}
};

利用 C艹 的特性,我们可以写得简练一点:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
bool canConstruct(string ransomNote, string magazine) {
vector<int> letter_map(128, 0);
for(char item : magazine) {
letter_map[item]++;
}

for(char item : ransomNote) {
if(--letter_map[item] < 0) {
return false;
}
}
return true;
}
};

解决方案2(Java)


1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class Solution {
public boolean canConstruct(String ransomNote, String magazine) {
int[] map_char_int = new int[26];
for (int i = 0; i < magazine.length(); i++) {
map_char_int[magazine.charAt(i)-'a']++;
}
for (int i = 0; i < ransomNote.length(); i++) {
if(--map_char_int[ransomNote.charAt(i)-'a'] < 0) {
return false;
}
}
return true;
}
}

解决方案3(Python)


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution(object):
def canConstruct(self, ransomNote, magazine):
"""
:type ransomNote: str
:type magazine: str
:rtype: bool
"""
ransomNoteSet, magazineSet = set(ransomNote), set(magazine)

if not ransomNoteSet.issubset(magazineSet):
return False

for item in ransomNoteSet:
if ransomNote.count(item) > magazine.count(item):
return False

return True

相关问题


题目来源