
问题
给定两个字符串 s 和 t ,编写一个函数来判断 t 是否是 s 的一个字母异位词。
输入: s = “anagram”, t = “nagaram”
输出: true
输入: s = “rat”, t = “car”
输出: false
说明:你可以假设字符串只包含小写字母。
进阶:如果输入字符串包含 unicode 字符怎么办?你能否调整你的解法来应对这种情况?
Given two strings s and t , write a function to determine if t is an anagram of s.
Input: s = “anagram”, t = “nagaram”
Output: true
Input: s = “rat”, t = “car”
Output: false
Note:You may assume the string contains only lowercase alphabets.
Follow up:What if the inputs contain unicode characters? How would you adapt your solution to such case?
示例
public class Program { public static void Main(string[] args) { string s = "anagram"; string t = "nagaram"; var res = IsAnagram(s, t); Console.WriteLine(res); s = "rat"; t = "car"; res = IsAnagram2(s, t); Console.WriteLine(res); s = "program"; t = "pragrom"; res = IsAnagram3(s, t); Console.WriteLine(res); s = "var"; t = "char"; res = IsAnagram4(s, t); Console.WriteLine(res); Console.ReadKey(); } private static bool IsAnagram(string s, string t) { //排序比较法 if(s.Length != t.Length) return false; var s2 = s.ToList(); s2.Sort(); var t2 = t.ToList(); t2.Sort(); for(var i = 0; i < s2.Count; i++) { if(s2[i] != t2[i]) return false; } return true; } private static bool IsAnagram2(string s, string t) { //数组记录法 var s2 = new int[26]; var t2 = new int[26]; foreach(var c in s) { s2[c - 97]++; } foreach(var c in t) { t2[c - 97]++; } for(var i = 0; i < 26; i++) { if(s2[i] != t2[i]) return false; } return true; } private static bool IsAnagram3(string s, string t) { //IsAnagram2的变种优化写法 var s2 = new int[26]; foreach(var c in s) { s2[c - 97]++; } foreach(var c in t) { s2[c - 97]--; } foreach(var item in s2) { if(item != 0) return false; } return true; } private static bool IsAnagram4(string s, string t) { //哈希法 var dic = new Dictionary<int, int>(); foreach(var c in s) { if(dic.ContainsKey(c - 97)) { dic[c - 97]++; } else { dic[c - 97] = 1; } } foreach(var c in t) { if(dic.ContainsKey(c - 97)) { dic[c - 97]--; } else { dic[c - 97] = 1; } } foreach(var item in dic) { if(item.Value != 0) return false; } return true; } }
以上给出4种算法实现,以下是这个案例的输出结果:
True False True False
分析:
显而易见,IsAnagram 的时间复杂度基于所使用的排序算法,其它3种算法的时间复杂度均为: 。
本文由 .Net中文网 原创发布,欢迎大家踊跃转载。
转载请注明本文地址:https://www.byteflying.com/archives/4040。