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 字符怎么办？你能否调整你的解法来应对这种情况？

  ●  难度: 简单

思路:
方法1: 分别进行排序后，判断序列是否相等。time: O ( n ⋅ l o g n ) 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.


方法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 <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.