383.赎金注
#100daysofcode #java #leetcode #strings

问题语句:
给定两个字符串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由小写英文字母组成。

解决方案:
算法:

  1. 创建一个大小26的数组,以存储每个字符的频率。
  2. 穿过杂志字符串并递增数组中每个字符的频率。
  3. 穿过ransomnote字符串并降低阵列中每个字符的频率。
  4. 如果数组中任何字符的频率变为负,请返回false。
  5. 返回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)由于数组的大小是恒定的。