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 方法一：先排序后再進行匹配；
class Solution {public: bool canConstruct(string ransomNote, string magazine) { sort(ransomNote.begin(), ransomNote.end()); sort(magazine.begin(), magazine.end()); int i = 0; int j = 0; while(i < ransomNote.length() && j < magazine.length()){ if(ransomNote[i] == magazine[j]){ cout << ransomNote[i] << endl;; i++; } j++; } if(i == ransomNote.length()) return 1; else return 0; }};方法二： 使用標記數組A，因為可能出現的字符只有26個（是有限的）。A中的元素表示magazine中相應字符出現的次數.
class Solution {public: bool canConstruct(string ransomNote, string magazine) { int A[26] = {0}; int rlen = ransomNote.length(); int mlen = magazine.length(); for(int i = 0; i < mlen; i++) ++A[magazine[i] - 'a']; for(int j = 0; j < rlen; j++){ if(--A[ransomNote[j] - 'a'] < 0) return 0; } return 1; }};新聞熱點
疑難解答
