| 2024-04-10 |

# 有效字母异位词

前言：简单题字典类型空间换时间直接秒

# 题目：

给定两个字符串 *s* 和 *t* ，编写一个函数来判断 *t* 是否是 *s* 的字母异位词。

** 注意：** 若 *s* 和 *t* 中每个字符出现的次数都相同，则称 *s* 和 *t* 互为字母异位词。

示例 1:
1
2
输入: s = "anagram", t = "nagaram"
输出: true
示例 2:
1
2
输入: s = "rat", t = "car"
输出: false
提示:

1 <= s.length, t.length <= 5 * 104

s 和 t 仅包含小写字母

进阶: 如果输入字符串包含 unicode 字符怎么办？你能否调整你的解法来应对这种情况？

# 题解

public class Solution {
    public bool IsAnagram(string s, string t) {
        Dictionary<char,int> wordAndShowtime = new();
        //把26个字母放进字典

        // 遍历26个字母，将它们与对应的数值放入字典中
        for (char letter = 'a'; letter <= 'z'; letter++)
        {
            // 将字母与对应的数值放入字典中
            wordAndShowtime[letter] = 0;
        }


        for(int i= 0;i<s.Length;i++){
            wordAndShowtime[s[i]]++;
        }

        for(int i= 0;i<t.Length;i++){
            wordAndShowtime[t[i]]--;
        }
        int sum =0;
        foreach(int num in wordAndShowtime.Values){
            if(num != 0)
            return false;
        }
        if(sum == 0){
            return true;
        }else{
            return false;
        }

    }
}

我这里用了一个字典

但如果是字符串包含 unicode 字符那么就需要两个字典来记录两个字符串中出现的字符了

public class Solution {
    public bool IsAnagram(string s, string t) {
        // 初始化字符及其出现次数的字典
        Dictionary<char, int> charCountS = new Dictionary<char, int>();
        Dictionary<char, int> charCountT = new Dictionary<char, int>();

        // 统计字符串 s 中各字符的出现次数
        CountCharacters(s, charCountS);

        // 统计字符串 t 中各字符的出现次数
        CountCharacters(t, charCountT);

        // 比较两个字典中字符出现次数是否一致
        return AreDictionariesEqual(charCountS, charCountT);
    }

    private void CountCharacters(string str, Dictionary<char, int> charCount) {
        foreach (char c in str) {
            if (charCount.ContainsKey(c)) {
                charCount[c]++;
            } else {
                charCount[c] = 1;
            }
        }
    }

    private bool AreDictionariesEqual(Dictionary<char, int> dict1, Dictionary<char, int> dict2) {
        if (dict1.Count != dict2.Count) {
            return false;
        }

        foreach (var kvp in dict1) {
            char key = kvp.Key;
            int value1 = kvp.Value;

            if (!dict2.ContainsKey(key) || dict2[key] != value1) {
                return false;
            }
        }

        return true;
    }
}

字典需要的空间还是挺大的

代码随想录中提供了数组版本

public bool IsAnagram(string s, string t) {
         int sl=s.Length,tl=t.Length;
        if(sl!=tl) return false;
        int[] a = new int[26];
     // 并不需要记住字符a的ASCII，只要求出一个相对数值就可以了
        for(int i = 0; i < sl; i++){
             a[s[i] - 'a']++;
             a[t[i] - 'a']--;
        }       
        foreach (int i in a)
        {
            // record数组如果有的元素不为零0，说明字符串s和t 一定是谁多了字符或者谁少了字符。
            if (i != 0)
                return false;
        }
        return true;
    }

好了今晚早点休息肚子痛。。。。

tags: #算法