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⋅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.