1
2
3
4
5
6
7
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

题意：题目叫做Ransom Note，勒索信，刚开始我还没理解这个题目的意思，尤其这个标题，和magazine有啥关系呢？后来仔细想想，才慢慢理解。勒索信，为了不暴露字迹，就从杂志上搜索各个需要的字母，组成单词来表达的意思。这样来说，题目也就清晰了，判断杂志上的字是否能够组成勒索信需要的那些字符。 
这里需要注意的就是杂志上的字符只能被使用一次，不过不用考虑大小写的问题。 
有一种最简单的理解就是对于ransomNote里每个字符出现的次数必须小于或者等于该字符在magazine出现的次数。

原文：http://blog.csdn.net/styshoo/article/details/52232993

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public  class  Solution {
     public  boolean  canConstruct(String ransomNote, String magazine) {
         int [] hash1= new  int [ 26 ];
         int [] hash2= new  int [ 26 ];
         for ( int  i= 0 ;i<ransomNote.length();i++){
             hash1[ransomNote.charAt(i)- 'a' + 0 ]++;
         }
         for ( int  i= 0 ;i<magazine.length();i++){
             hash2[magazine.charAt(i)- 'a' ]++;
         }
         for ( int  i= 0 ;i< 26 ;i++){
             if (hash1[i]>hash2[i])
                 return  false ;
             else
                 continue ;
         }
         return  true ;
     }
}

PS:用的hashmap.分别遍历信件和杂志，得到出现的字母的次数。若杂志对应次数小于信件的话，false。下面是leetcode上比较火的？原理差不多。就是代码精简！！！

1
2
3
4
5
6
7
8
9
10
  public  boolean  canConstruct(String ransomNote, String magazine) {  
        int [] arr =  new  int [ 26 ];       
         for  ( int  i =  0 ; i < magazine.length(); i++) {
             arr[magazine.charAt(i) -  'a' ]++;
         }        
         for  ( int  i =  0 ; i < ransomNote.length(); i++) { 
            if (--arr[ransomNote.charAt(i)- 'a' ] <  0 ) {                 return  false ;
             }
         }  return  true ;
     }