LEETCODE--Ransom Note

2019-11-14 12:55:27

字体：大中小

来源：转载

供稿：网友

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; }};

上一篇：进程缓冲区和内核缓冲区

下一篇：ZJU 2932 The Seven Percent Solution（模拟）