当前位置：首页 > article >正文

判断一个字符串能否被另外一个字符串中的元素构成

article 2025/1/30 13:12:43

给你两个字符串：ransomNote 和 magazine ，判断 ransomNote 能不能由 magazine 里面的字符构成。如果可以，返回 true ；否则返回 false 。 magazine 中的每个字符只能在 ransomNote 中使用一次。(字符串只能由字母构成，且长度均大于0)

以下是几种判断 ransomNote 能否由 magazine 里面的字符构成的 Java 实现方法：

方法一：使用数组统计字符频率

由于字符串只包含小写字母，因此可以使用一个长度为 26 的数组来统计每个字符的出现次数。

public class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        // 因为只包含小写字母，创建一个长度为 26 的数组来统计字符频率
        int[] charCount = new int[26];

        // 统计 magazine 中每个字符的出现次数
        for (char c : magazine.toCharArray()) {
            charCount[c - 'a']++;
        }

        // 检查 ransomNote 中的字符是否都能在 magazine 中找到
        for (char c : ransomNote.toCharArray()) {
            if (--charCount[c - 'a'] < 0) {
                return false;
            }
        }

        return true;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        String ransomNote = "a";
        String magazine = "b";
        System.out.println(solution.canConstruct(ransomNote, magazine)); 
    }
}

复杂度分析：

时间复杂度：，其中是 ransomNote 的长度，是 magazine 的长度。需要分别遍历两个字符串。
空间复杂度：，因为只使用了一个长度为 26 的数组，额外空间是常数级的。

方法二：使用 HashMap 统计字符频率

使用 HashMap 来统计字符的出现次数，适用于字符串包含更多种类字符的情况。

import java.util.HashMap;
import java.util.Map;

public class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        // 创建一个 HashMap 来统计 magazine 中每个字符的出现次数
        Map<Character, Integer> charCount = new HashMap<>();

        // 统计 magazine 中每个字符的出现次数
        for (char c : magazine.toCharArray()) {
            charCount.put(c, charCount.getOrDefault(c, 0) + 1);
        }

        // 检查 ransomNote 中的字符是否都能在 magazine 中找到
        for (char c : ransomNote.toCharArray()) {
            if (!charCount.containsKey(c) || charCount.get(c) == 0) {
                return false;
            }
            charCount.put(c, charCount.get(c) - 1);
        }

        return true;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        String ransomNote = "aa";
        String magazine = "ab";
        System.out.println(solution.canConstruct(ransomNote, magazine)); 
    }
}

复杂度分析：

时间复杂度：，同样需要分别遍历两个字符串。
空间复杂度：，其中是 magazine 中不同字符的数量。在最坏情况下，所有字符都不同，最大为字符串的长度。

方法三：暴力解法

对于 ransomNote 中的每个字符，在 magazine 中查找并标记已使用的字符。

public class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        char[] magazineChars = magazine.toCharArray();

        for (char c : ransomNote.toCharArray()) {
            boolean found = false;
            for (int i = 0; i < magazineChars.length; i++) {
                if (magazineChars[i] == c) {
                    // 标记该字符已使用
                    magazineChars[i] = ' ';
                    found = true;
                    break;
                }
            }
            if (!found) {
                return false;
            }
        }

        return true;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        String ransomNote = "a";
        String magazine = "b";
        System.out.println(solution.canConstruct(ransomNote, magazine)); 
    }
}

复杂度分析：