Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Finding Substring Anagrams
using System;
using System.Collections.Generic;
using System.Linq;
public static class AnagramInSingleWord
{
private static void AddToSubstringDictionary(
string s, Tuple<int, int> startAndLength,
IDictionary<Tuple<int, int>, string> substrings
)
{
if (startAndLength.Item2 > 0 && substrings.TryGetValue(startAndLength, out string substring) == false)
{
substrings.Add(startAndLength, s.Substring(startAndLength.Item1, startAndLength.Item2));
}
}
private static void GenerateSubStrings(
string s,
Tuple<int, int> startAndLength,
IDictionary<Tuple<int, int>, string> substrings
)
{
if (substrings.ContainsKey(startAndLength))
{
return;
}
if (startAndLength.Item2 == 0)
{
return;
}
Tuple<int, int> chompLeftCoordinates = Tuple.Create(startAndLength.Item1 + 1, startAndLength.Item2 - 1);
Tuple<int, int> chompRightCoordinates = Tuple.Create(startAndLength.Item1, startAndLength.Item2 - 1);
GenerateSubStrings(s, chompLeftCoordinates, substrings);
GenerateSubStrings(s, chompRightCoordinates, substrings);
AddToSubstringDictionary(s, chompLeftCoordinates, substrings);
AddToSubstringDictionary(s, chompRightCoordinates, substrings);
}
private static bool IsPairAccountedFor(
Tuple<int, int> a,
Tuple<int, int> b,
HashSet<HashSet<Tuple<int, int>>> pairs
)
{
foreach (HashSet<Tuple<int, int>> pair in pairs)
{
if (pair.Contains(a) && pair.Contains(b))
{
return true;
}
}
return false;
}
private static bool IsAnagram(string a, string b, IDictionary<string, HashSet<string>> anagramBagMap)
{
if (a.Length != b.Length)
{
return false;
}
if (anagramBagMap.TryGetValue(a, out HashSet<string> anagramBag))
{
if (anagramBag.Contains(b))
{
return true;
}
}
IDictionary<char, int> aCharMap = new Dictionary<char, int>();
IDictionary<char, int> bCharMap = new Dictionary<char, int>();
for (int i = 0; i < a.Length; i++)
{
if (aCharMap.ContainsKey(a[i]) == false)
{
aCharMap.Add(a[i], 0);
}
aCharMap[a[i]] += 1;
if (bCharMap.ContainsKey(b[i]) == false)
{
bCharMap.Add(b[i], 0);
}
bCharMap[b[i]] += 1;
}
foreach (var kvp in aCharMap)
{
if (bCharMap.TryGetValue(kvp.Key, out int numCharsInB) == false || kvp.Value != numCharsInB)
{
return false;
}
}
if (anagramBagMap.TryGetValue(a, out HashSet<string> aStringAnagramBag) == false)
{
aStringAnagramBag = new HashSet<string>();
anagramBagMap.Add(a, aStringAnagramBag);
}
aStringAnagramBag.Add(b);
if (anagramBagMap.TryGetValue(b, out HashSet<string> bStringAnagramBag) == false)
{
bStringAnagramBag = new HashSet<string>();
anagramBagMap.Add(b, bStringAnagramBag);
}
bStringAnagramBag.Add(a);
return true;
}
public static int NumberOfAnagrams(string s)
{
IDictionary<Tuple<int, int>, string> substrings = new Dictionary<Tuple<int, int>, string>();
GenerateSubStrings(s, Tuple.Create(0, s.Length), substrings);
HashSet<HashSet<Tuple<int, int>>> anagramPairs = new HashSet<HashSet<Tuple<int, int>>>();
IDictionary<string, HashSet<string>> anagramBag = new Dictionary<string, HashSet<string>>();
foreach (KeyValuePair<Tuple<int, int>, string> substringTuple in substrings)
{
foreach (KeyValuePair<Tuple<int, int>, string> otherSubstringTuple in substrings.Where(t => t.Key.Equals(substringTuple.Key) == false))
{
if (IsPairAccountedFor(substringTuple.Key, otherSubstringTuple.Key, anagramPairs) == false &&
IsAnagram(substringTuple.Value, otherSubstringTuple.Value, anagramBag))
{
var localPair = new HashSet<Tuple<int, int>>();
localPair.Add(substringTuple.Key);
localPair.Add(otherSubstringTuple.Key);
anagramPairs.Add(localPair);
}
}
}
return anagramPairs.Count();
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment