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.

1
2
3
canConstruct("a","b") -> false
canConstruct("aa","ab") -> false
canConstruct("aa","aab") -> true

分析

题目的大意是:给定一个字符串A,然后再给定一个字符串B。要求如果A字符串能够从B字符串的字符中构造,那么返回true,否则返回false。
可以忽略大小写;B字符串中的每个字符只能使用一次。

大家是否还记得上次的题目:3. Longest Substring Without Repeating Characters
在这个题目中,我们将字符转换成ASCII码,从而很巧妙地解决了问题。在这个问题中,我们同样可以采用将字符转换成ASCII码的方式解决。

我们在这里把题目转换一下:任意在字符串A中出现的字符,字符串B必须包含且出现次数大于等于该字符在A中出现的次数!

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public class Solution {
public boolean canConstruct(String ransomNote, String magazine) {
if (ransomNote.length() > magazine.length()) {
return false;
} else {
int[] ransomChars = new int[26];
int[] magazineChars = new int[26];
for (int i = 0; i < ransomNote.length(); i++) {
ransomChars[ransomNote.charAt(i) - 97] += 1;
}
for (int i = 0; i < magazine.length(); i++) {
magazineChars[magazine.charAt(i) - 97] += 1;
}
for (int i = 0; i < ransomChars.length; i++) {
if (ransomChars[i] > magazineChars[i]) {
return false;
}
}
return true;
}
}