LeetCode 383. 赎金信

Categories:

题目描述
思路分析
1. 解法一：字符计数（推荐）
相似题目

题目描述

✅ 383. 赎金信

思路分析

解法一：字符计数（推荐）

核心思路：

先统计 magazine 中每个字母出现次数。

遍历 ransomNote，每用掉一个字母就递减计数，若出现负数说明无法构成。

字母集为 26 个小写字母，计数数组常数大小。

复杂度分析：

时间复杂度：O(m + n)，其中 m、n 分别表示两个字符串长度。

空间复杂度：O(1)，仅使用长度为 26 的计数数组。

class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        int[] cnt = new int[26];

        for (int i = 0; i < magazine.length(); i++) {
            cnt[magazine.charAt(i) - 'a']++;
        }

        for (int i = 0; i < ransomNote.length(); i++) {
            int idx = ransomNote.charAt(i) - 'a';
            cnt[idx]--;
            if (cnt[idx] < 0) {
                return false;
            }
        }

        return true;
    }
}

func canConstruct(ransomNote string, magazine string) bool {
	var cnt [26]int

	for i := 0; i < len(magazine); i++ {
		cnt[magazine[i]-'a']++
	}

	for i := 0; i < len(ransomNote); i++ {
		idx := ransomNote[i] - 'a'
		cnt[idx]--
		if cnt[idx] < 0 {
			return false
		}
	}

	return true
}

相似题目

题目	难度	考察点
242. 有效的字母异位词	简单	计数
409. 最长回文串	简单	计数
387. 字符串中的第一个唯一字符	简单	计数
567. 字符串的排列	中等	计数
438. 找到字符串中所有字母异位词	中等	滑动窗口

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2022/77482586