问题语句:
给定两个字符串ransomnote和杂志,如果可以使用杂志的字母和false否则,则返回true。
杂志中的每个字母只能在Ransomnote中使用一次。
示例1:
输入: ransomnote =“ a”,杂志=“ b”
输出: false
示例2:
输入: ransomnote =“ aa”,杂志=“ ab”
输出: false
示例3:
输入: ransomnote =“ aa”,杂志=“ aab”
输出: true
约束:
- 1 <= ransomnote.length,magazine.length <= 105
- Ransomnote和Magazine由小写英文字母组成。
解决方案:
算法:
- 创建一个大小26的数组,以存储每个字符的频率。
- 穿过杂志字符串并递增数组中每个字符的频率。
- 穿过ransomnote字符串并降低阵列中每个字符的频率。
- 如果数组中任何字符的频率变为负,请返回false。
- 返回true。
代码:
public class Solution {
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;
}
时间复杂性:
o(n+m),其中n是勒索的长度,m是杂志的长度。
空间复杂性:
o(1)由于数组的大小是恒定的。