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

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\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 <kbd>43.61%</kbd> of csharp submissions.

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 <kbd>99.69%</kbd> 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 <kbd>77.57%</kbd> of csharp submissions.