383. 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.

canConstruct(“a”, “b”) -> false
canConstruct(“aa”, “ab”) -> false
canConstruct(“aa”, “aab”) -> true

思路:不需要考虑顺序,只要考虑出现的字母,跟每个字母的出现次数,而且题目限定出现的字母都是lowercase。 那magazine中每个字母出现次数>= ransom中每个字母出现次数,就返回true. 我们可以用长度26的数组来实现。 统计每个字母在magazine的出现次数,

public class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        if (ransomNote == null || magazine == null) return false;
        int[] dict = new int[26];
        for (int i = 0; i < magazine.length();i++) {
            int pos = magazine.charAt(i) - 'a';
            dict[pos] += 1;
        }

        for (int j = 0; j < ransomNote.length(); j++) {
            int pos = ransomNote.charAt(j) - 'a';
            dict[pos] -=1;
            if (dict[pos] < 0) {
                return false;
            }
        }
        return true;

    }
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s