242-有效的字母异位词.md

title	date	tags	categories
242.有效的字母异位词	2019-05-31 10:31:51 -0700	leetcode	算法学习 leetcode

题目

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

示例 1:

输入: s = "anagram", t = "nagaram"
输出: true

示例 2:

输入: s = "rat", t = "car"
输出: false

说明: 你可以假设字符串只包含小写字母。

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

思路

首先要知道什么是字母异位词,它是指两个字符串所包含的字母的出现次数都相同,只是顺序不一样.

这道题解决的思路还是挺多的,而且虽然说明上明确只有小写字母,但是进阶里问到如果出现unicode字符怎么办,所以方法里最好不要有硬编码26个字母出现.

• 方法一:将两个字符串直接排序,然后逐个比较对应位置是否相同.
• 方法二:s字符串里面每出现一个字母,就在字典对应位置+1;t字符串里每出现一个字母,就在对应位置-1,这样一加一减,结果就应该是字典里面所有数据都为0,如果不是,说明两者不是字母异位词.

代码

排序法:

public bool IsAnagram(string s, string t)
{
    if (s.Length != t.Length)
    {
        return false;
    }
    char[] str1 = s.ToCharArray();
    char[] str2 = t.ToCharArray();
    Array.Sort(str1);
    Array.Sort(str2);
    for (int i = 0; i < str1.Length; i++)
    {
        if (str1[i] != str2[i])
        {
            return false;
        }
    }
    return true;
}

字典法:

public bool IsAnagram(string s, string t)
{
    if (s.Length != t.Length)
    {
        return false;
    }
    var charDict = new Dictionary<char, int>();
    foreach (var c in s)
    {
        if (charDict.ContainsKey(c))
        {
            charDict[c]++;
        }
        else
        {
            charDict.Add(c, 1);
        }
    }
    foreach (var c in t)
    {
        if (charDict.ContainsKey(c))
        {
            if (--charDict[c] == 0)
            {
                charDict.Remove(c);
            }
        }
        else
        {
            return false;
        }
    }
    return charDict.Count == 0;
}