Geek Answers Handbook

Given two lines, one is an anagram of the other

I just started to learn "Cracking the Coding Interview" and have the following solution to this problem:

public static bool isAnagram(String s, String t) { if (s == "" || t == "") return false; else if (s.Length != t.Length) return false; int[] letters = new int[256]; char[] s_array = s.ToCharArray(); foreach(char c in s_array) { letters[c]++; } for (int i = 0; i < t.Length; i++) { int c = t[i]; if (--letters[c] < 0) { return false; } } return true; }

This is an almost verbatim solution from the book, only in C #, not Java, as well as some additional nullchecks. I also solved the issue using LINQ, but wanted an additional solution that did not include sorting.

Can this approach be made more elegant? The code works very well, I just want to know if there is a more elegant or better solution there. Thanks!!

+6
source share
8 answers

This code should work for you:

 public static bool IsAnagram(string s1, string s2) { if (string.IsNullOrEmpty(s1) || string.IsNullOrEmpty(s2)) return false; if (s1.Length != s2.Length) return false; foreach (char c in s2) { int ix = s1.IndexOf(c); if (ix >= 0) s1 = s1.Remove(ix, 1); else return false; } return string.IsNullOrEmpty(s1); }

Edit: Added version without linq.

You can also add additional checks for null and null values ​​and move the solution to StringBuilder for better performance, but the purpose of the code is clear.

+15
source

As you asked for a more elegant solution, perhaps this meets your needs - more compact, written as an extension method:

 public static bool IsAnagram(this string s1, string s2) { if (s1.Length == s2.Length) { var count = new int[1024]; foreach (var c in s1) { ++count[c]; } return s2.All(t => --count[c] >= 0); } return false; } var result = "mary".IsAnagram("army");
+4
source

In order to correctly handle all Unicode characters (since Char is a UTF-16 code unit), I can't think of an efficient way. But I will try with the correct one:

 public static bool isAnagram(String s, String t) { s = s.Normalize(); t = t.Normalize(); if (s == "" || t == "") return false; else if (s.Length != t.Length) return false; while (s.Length > 0) { char first = s[0]; string search = new string(first, 1); if (Char.IsHighSurrogate(first)) { char second = s[1]; //Assumed to work - if it doesn't, the input was malformed search = new string(new char[] { first, second }); } int index = t.IndexOf(search); if (index < 0) return false; t = (index > 0 ? t.Substring(0, index) : "") + t.Substring(index + search.Length); s = s.Substring(search.Length); } return true; }

Otherwise, if you want to continue using the array of counters ( letters ), you must use an array that can contain at least 1114112 elements, and you still need to correctly handle surrogates.

+3
source

You can sort both lines and compare

+2
source

How about this solution without linq?

 public static bool IsAnagram(String s, String t) { if ((s == null) || (t == null) || (s.Length == 0) || (t.Length == 0) || (s.Length != t.Length)) return false; var ta = t.ToCharArray(); foreach (char ch in s) { int x = Array.IndexOf(ta, ch); if (x < 0) return false; ta[x] = '\0'; } return true; }
+2
source

Dictionary based solution. Separate each line by counting char, and then do a compareison of the dictionary (note that this method is in my head):

 class Program { static void Main(string[] args) { Console.WriteLine("jon skeet".PermutationOf("jokes net")); Console.WriteLine(new[] { 5, 2, 3, 4, 5 }.PermutationOf(new[] { 5, 4, 5, 2, 3 })); Console.Read(); } } public static class Extensions { public static bool IsPermutationOf<T>(this IEnumerable<T> source1, IEnumerable<T> source2) { return source1.IsPermutationOf(source2, EqualityComparer<T>.Default); } public static bool IsPermutationOf<T>(this IEnumerable<T> source1, IEnumerable<T> source2, EqualityComparer<T> comparer) { return source1.Decompose(comparer).DictionaryEqual(source2.Decompose(comparer)); } public static Dictionary<T, int> Decompose<T>(this IEnumerable<T> source, EqualityComparer<T> comparer) { return source.GroupBy(t => t, comparer).ToDictionary(t => t.Key, t => t.Count(), comparer); } public static bool DictionaryEqual<TKey, TValue>(this IDictionary<TKey, TValue> first, IDictionary<TKey, TValue> second) { return first.Count == second.Count && !first.Except(second).Any(); } }

Please note that you can provide a custom char resolver to solve problems with uppercase / lowercase letters.

I went a little further by renaming IsAnagram to IsPermutationOf . Works for all kinds of list actually. Pretty useful and elegant in this way.

+1
source
  • Check if the lengths are equal, if not, they are not anagrams
  • Iterate over t
  • Check if current char exists from t to s , if not, they are not anagrams
  • If so, remove char from s

  • If the result is an empty string, this is anagram

     public static bool isAnagram(String s, String t) { if(s.Length != t.Length) return false; for(int i = 0; i < t.Length; i++) { var n = s.IndexOf(t[i]); if(n < 0) return false; s = s.Remove(n, 1); } return String.IsNullOrEmpty(s); }
+1
source

Sort and then compare the operation of the sequence:

 bool isAnagram = "asdf".OrderBy(c => c).SequenceEqual("fdsa".OrderBy(c => c));

Alternatively, you can use Dictionary<char, int> to track the number of characters (Unicode characters have more than 256 possible values). Also, you do not need to call ToArray() before iterating over the characters of a string.

0
source

More articles:


All Articles