Ransom Note
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.
Original url:leetcode Ransom Note
Analysis:
This is to count the number of characters in magazine and characters in ransom note. use haspmap or array. since note contains only lowercase letters, array is enought.
This is also a method to tell if a set is a subset of another set.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | public class Solution { public boolean canConstruct(String ransomNote, String magazine) { int[] cnt = new int[26]; //collect statistics of characters in magzine for (int i = 0; i < magazine.length(); i++){ cnt[magazine.charAt(i) - 97]++; } //consume the statistics by examing the ransom note for (int i = 0; i < ransomNote.length(); i++){ if (--cnt[ransomNote.charAt(i) - 97] < 0){ return false; } } return true; } } |
No comments:
Post a Comment