\u9898\u76ee\u5927\u610f\uff1a\u7ed9\u4f60\u4e00\u4e2a\u5b57\u7b26\u4e32\uff0c\u95ee\u80fd\u5426\u7528\u5b83\u5176\u4e2d\u7684\u5b57\u7b26\u7ec4\u6210\u53e6\u5916\u4e00\u4e2a\u5b57\u7b26\u4e32\uff0c\u6bcf\u4e2a\u5b57\u7b26\u53ea\u80fd\u4f7f\u7528\u4e00\u6b21\u3002<\/p>\n
Problem:<\/strong><\/p>\n 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.<\/p>\n Each letter in the magazine string can only be used once in your ransom note.<\/p>\n Note:<\/b> Solution: HashTable<\/strong><\/p>\n Time complexity: O(n + m)<\/p>\n Space complexity: O(128)<\/p>\n C++<\/p>\n <\/p>\n Python3<\/p>\n <\/p>\n","protected":false},"excerpt":{"rendered":" \u9898\u76ee\u5927\u610f\uff1a\u7ed9\u4f60\u4e00\u4e2a\u5b57\u7b26\u4e32\uff0c\u95ee\u80fd\u5426\u7528\u5b83\u5176\u4e2d\u7684\u5b57\u7b26\u7ec4\u6210\u53e6\u5916\u4e00\u4e2a\u5b57\u7b26\u4e32\uff0c\u6bcf\u4e2a\u5b57\u7b26\u53ea\u80fd\u4f7f\u7528\u4e00\u6b21\u3002 Problem: Given an arbitrary ransom note string and another string containing letters from all the magazines, write a function that will return true if…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[70],"tags":[254,8,222,82],"class_list":["post-2114","post","type-post","status-publish","format-standard","hentry","category-hashtable","tag-counter","tag-counting","tag-easy","tag-hashtable","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/2114","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=2114"}],"version-history":[{"count":4,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/2114\/revisions"}],"predecessor-version":[{"id":2118,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/2114\/revisions\/2118"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=2114"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=2114"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=2114"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}
\nYou may assume that both strings contain only lowercase letters.<\/p>\ncanConstruct(\"a\", \"b\") -> false\r\ncanConstruct(\"aa\", \"ab\") -> false\r\ncanConstruct(\"aa\", \"aab\") -> true<\/pre>\n
\/\/ Author: Huahua\r\n\/\/ Running time: 24 ms\r\nclass Solution {\r\npublic:\r\n bool canConstruct(string ransomNote, string magazine) {\r\n vector<int> counts(128, 0);\r\n for (const char c : magazine)\r\n ++counts[c];\r\n for (const char c : ransomNote)\r\n if (--counts[c] < 0) return false;\r\n return true;\r\n }\r\n};<\/pre>\n\/\/ Author: Huahua\r\n\/\/ Running time: 9 ms (beats 100%)\r\n\r\nstatic int x=[](){\r\n std::ios::sync_with_stdio(false);\r\n cin.tie(NULL);\r\n return 0;\r\n}();\r\n\r\nclass Solution {\r\npublic:\r\n bool canConstruct(const string& ransomNote, const string& magazine) {\r\n vector<int> counts(128, 0);\r\n for (const char c : magazine)\r\n ++counts[c];\r\n for (const char c : ransomNote)\r\n if (--counts[c] < 0) return false;\r\n return true;\r\n }\r\n};<\/pre>\n\"\"\"\r\nAuthor: Huahua\r\nRunning time: 64 ms\r\n\"\"\"\r\nclass Solution:\r\n def canConstruct(self, ransomNote, magazine):\r\n return not collections.Counter(ransomNote) - collections.Counter(magazine);\r\n<\/pre>\n