Two strings are both lowercase letters. Write a function to determine if one string can be constructed using the letters from the other string. For example:
1 2 3 | canConstruct("aa", "ab") = false canConstruct("aa", "aab") = true canConstruct("a", "b") = false |
canConstruct("aa", "ab") = false
canConstruct("aa", "aab") = true
canConstruct("a", "b") = falseSubmit your solution at: https://leetcode.com/problems/ransom-note/
Using STL::unordered_map
STL::unordered_map can be seen as an efficient hash data structure. We can record the count of each lowercase appearance and use them by decrementing each counter. If we have a negative counter, it means we cannot construct the note by using the characters from the other string.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 | class Solution { public: bool canConstruct(string ransomNote, string magazine) { unordered_map<char, int> mag; for (char x: magazine) { if (mag.count(x)) { mag[x] ++; } else { mag[x] = 1; } } for (char x: ransomNote) { if (mag.count(x)) { mag[x] --; if (mag[x] < 0) { return false; } } else { return false; } } return true; } }; |
class Solution {
public:
bool canConstruct(string ransomNote, string magazine) {
unordered_map<char, int> mag;
for (char x: magazine) {
if (mag.count(x)) {
mag[x] ++;
} else {
mag[x] = 1;
}
}
for (char x: ransomNote) {
if (mag.count(x)) {
mag[x] --;
if (mag[x] < 0) {
return false;
}
} else {
return false;
}
}
return true;
}
};Using Static Array
Since the given inputs are all lowercase letters, we can construct the counter of 26 elements and implement the same idea but shorter.
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) { int mag[26] = {0}; for (char x: magazine) { mag[x - 97] ++; } for (char x: ransomNote) { mag[x -97] --; if (mag[x - 97] < 0) { return false; } } return true; } }; |
class Solution {
public:
bool canConstruct(string ransomNote, string magazine) {
int mag[26] = {0};
for (char x: magazine) {
mag[x - 97] ++;
}
for (char x: ransomNote) {
mag[x -97] --;
if (mag[x - 97] < 0) {
return false;
}
}
return true;
}
};–EOF (The Ultimate Computing & Technology Blog) —
GD Star Rating
loading...
291 wordsloading...
Last Post: How to Prolong Battery Use when Playing Pokemon?
Next Post: How to Define Lambda Functions in C++11?
