题目大意：给你一个字符串，问能否用它其中的字符组成另外一个字符串，每个字符只能使用一次。
Problem:
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
Solution: HashTable
Time complexity: O(n + m)
Space complexity: O(128)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
// Author: Huahua // Running time: 24 ms class Solution { public: bool canConstruct(string ransomNote, string magazine) { vector<int> counts(128, 0); for (const char c : magazine) ++counts[c]; for (const char c : ransomNote) if (--counts[c] < 0) return false; return true; } }; |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
// Author: Huahua // Running time: 9 ms (beats 100%) static int x=[](){ std::ios::sync_with_stdio(false); cin.tie(NULL); return 0; }(); class Solution { public: bool canConstruct(const string& ransomNote, const string& magazine) { vector<int> counts(128, 0); for (const char c : magazine) ++counts[c]; for (const char c : ransomNote) if (--counts[c] < 0) return false; return true; } }; |
Python3
|
1 2 3 4 5 6 7 |
""" Author: Huahua Running time: 64 ms """ class Solution: def canConstruct(self, ransomNote, magazine): return not collections.Counter(ransomNote) - collections.Counter(magazine); |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Paypal
Venmo
huahualeetcode
huahualeetcode
微信打赏
Be First to Comment