贖金信
-
給你兩個字符串：ransomNote 和 magazine ，判斷 ransomNote 能不能由 magazine 里面的字符構成。
-
如果可以，返回 true ；否則返回 false 。
magazine 中的每個字符只能在 ransomNote 中使用一次。
解題思路
可以使用哈希表來解決這個問題。
- 1、首先遍歷 magazine，將每個字符及其出現次數存儲在哈希表中。
- 2、 遍歷 ransomNote，對于每個字符，在哈希表中查找其出現次數，如果出現次數大于 0， 則將其出現次數減 1；如果出現次數為 0 或者字符在哈希表中不存在，則返回 false。
- 3、 如果遍歷完成，則返回 true。
Java實現
public class RansomNote {public boolean canConstruct(String ransomNote, String magazine) {Map<Character, Integer> charCounts = new HashMap<>();// 統計 magazine 中每個字符的出現次數for (char ch : magazine.toCharArray()) {charCounts.put(ch, charCounts.getOrDefault(ch, 0) + 1);}// 遍歷 ransomNote，檢查每個字符是否能在 magazine 中找到for (char ch : ransomNote.toCharArray()) {if (!charCounts.containsKey(ch) || charCounts.get(ch) == 0) {return false;}charCounts.put(ch, charCounts.get(ch) - 1);}return true;}public static void main(String[] args) {RansomNote ransomNote = new RansomNote();String ransomNote1 = "a", magazine1 = "b";System.out.println("Test Case 1:");System.out.println("ransomNote: \"a\", magazine: \"b\"");System.out.println("Result: " + ransomNote.canConstruct(ransomNote1, magazine1)); // Expected: falseString ransomNote2 = "aa", magazine2 = "ab";System.out.println("\nTest Case 2:");System.out.println("ransomNote: \"aa\", magazine: \"ab\"");System.out.println("Result: " + ransomNote.canConstruct(ransomNote2, magazine2)); // Expected: false}
}
時間空間復雜度
- 時間復雜度： 遍歷 magazine 字符串并統計字符出現次數的時間復雜度為 O(m)，遍歷 ransomNote 字符串并檢查是否能在 magazine 中找到的時間復雜度為 O(n)，總體時間復雜度為 O(m+n)。
- 空間復雜度： 使用了哈希表來存儲 magazine 中每個字符的出現次數，空間復雜度為 O(m)，其中 m 是 magazine 字符串的長度。
