題目

#

leetcode 242 - Valid Anagram (題目說明請點連結)

題目簡述

#

判斷兩個字串是否為有效的字母異位詞。

範例

#

Example 1:

Input: s = "anagram", t = "nagaram"
Output: true
Explanation: "anagram" 和 "nagaram" 是有效的字母異位詞。

Example 2:

Input: s = "rat", t = "car"
Output: false
Explanation: "rat" 和 "car" 不是有效的字母異位詞。

解題思路

#

這題要求我們判斷兩個字串是否為有效的字母異位詞。字母異位詞是指兩個字串中每個字母出現的次數相同。我們可以使用 HashMap 來記錄第一個字串中每個字母的出現次數，然後遍歷第二個字串來檢查每個字母的出現次數是否一致。

解法

#

HashMap 計數法（HashMap Counting Approach）

1. 如果兩個字串長度不同，直接返回 false
2. 使用 HashMap 記錄第一個字串中每個字母的出現次數
3. 遍歷第二個字串，對每個字母：
   • 如果該字母不在 HashMap 中或次數為 0，返回 false
   • 否則將該字母的次數減 1
4. 如果所有字母的次數都匹配，返回 true

步驟

#

• 初始化：
  • 檢查字串長度是否相同
  • 創建 HashMap<Character, Integer> map
• 記錄字母次數：
  • 遍歷第一個字串，記錄每個字母的次數
• 檢查字母次數：
  • 遍歷第二個字串，檢查每個字母的次數
• 返回結果：
  • 如果所有字母的次數都匹配，返回 true

例子說明

#

s = "anagram", t = "nagaram"

完整程式碼

#

class Solution {
    public boolean isAnagram(String s, String t) {
        if(s.length() != t.length()) return false;

        // 使用HashMap記錄字母次數
        Map<Character, Integer> map = new HashMap<>();

        // 記錄s中的字母次數
        for(int i = 0; i < s.length(); i++){
            map.put(s.charAt(i), map.getOrDefault(s.charAt(i), 0) + 1);
        }

        // 檢查t中的字母次數
        for(int i = 0; i < t.length(); i++){
            char ch = t.charAt(i);

            if(!map.containsKey(ch) || map.get(ch) == 0){
                return false;
            }

            map.put(ch, map.get(ch) - 1);
        }

        return true;
    }
}

時間複雜度

#

• 時間複雜度：O(n)，其中 n 是字串的長度，需要遍歷所有字母
• 空間複雜度：O(1)，因為字母數量有限，HashMap 的大小不會超過 26