C#版[击败99.69%的提交] - Leetcode 242. 有效的同构异形词 - 题解

Enjoy233

发布于 2019-03-05 15:59:30

5290

发布于 2019-03-05 15:59:30

文章被收录于专栏：大白技术控的技术自留地

C#版 - Leetcode 242. 有效的同构异形词 - 题解

Leetcode 242.Valid Anagram

在线提交: https://leetcode.com/problems/valid-anagram/

题目描述

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的一个同构异形词(变位英文字符串)。

示例 1:

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

示例 2:

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

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

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

● 难度:	简单

通过次数：10.1K
提交次数：21.8K
贡献者：LeetCode
相关话题排序哈希表相似题目字母异位词分组 Palindrome Permutation 找到字符串中所有字母异位词

思路: 方法1: 分别进行排序后，判断序列是否相等。time: O(n⋅logn)O(n\cdot logn)O(n⋅logn), space: O(n)

方法2: 使用26位的字典，记录每一个字母出现的次数。 time: O(n), space: O(1)

方法1 已AC代码:

    public class Solution
    {
        public bool IsAnagram(string s, string t)
        {
            if (s.Length != t.Length)
                return false;

            char[] ch1 = s.ToCharArray();
            char[] ch2 = t.ToCharArray();
            Array.Sort(ch1);
            Array.Sort(ch2);

            return ch1.SequenceEqual(ch2);
        }
    }

Rank:

You are here! Your runtime beats 43.61% of csharp submissions.

方法2 已AC代码:

public class Solution
{
    public bool IsAnagram(string s, string t)
    {
        if (s.Length != t.Length)
            return false;

        int[] counts = new int[26];
        for(int i = 0;i < s.Length;i++)
        {
            counts[s[i]-'a']++;
            counts[t[i]-'a']--;
        }

        foreach (var count in counts)
            if (count != 0)
                return false;

        return true;
    }
}

Rank:

You are here! Your runtime beats 99.69% of csharp submissions.

方法2的另一写法:

public class Solution
{
    public bool IsAnagram(string s, string t)
    {
        if (s.Length != t.Length)
            return false;

        Dictionary<char, int> dict = new Dictionary<char, int>();
        for (int i = 0; i < s.Length; i++)
        {
            if(!dict.ContainsKey(s[i]))
                dict.Add(s[i], 1);
            else
                dict[s[i]]++;
        }

        for (int j = 0; j < t.Length; j++)
        {
            if (!dict.ContainsKey(t[j]) || --dict[t[j]] < 0)  // --dict[t[j]] < 0 用于判断从头扫描到尾，t中有没有出现次数多于s中的字符
               return false;
        }

        return true;
    }
}

Rank: You are here! Your runtime beats 77.57% of csharp submissions.

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2018年09月19日，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

编程算法

登录后参与评论

0 条评论

热度