Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Unique Prefixes
string[] words = new string[]
{"zebra","beard","duck","zest", "ducklin", "bearcat","dumb","beautiful","zebracrossing"};
//{ "zebra", "dog", "duck", "zimbawae", "zest","god","dove", "dig","got","dumb"};
Array.Sort(words);
Func<string, string, int> DiffersAt = (a, b) =>
{
int m = a.Length;
int n = b.Length;
int length = Math.Min(m, n);
for (int i = 0; i < length; i++)
{
if (a[i] != b[i])
return i;
}
return length;
};
List<KeyValuePair<string, string>> pairs =
new List<KeyValuePair<string, string>>();
for (int i = 0; i < words.Length - 1; i++)
{
int mismatchAt = DiffersAt(words[i], words[i + 1]);
pairs.Add(new KeyValuePair<string, string>(words[i],
words[i].Substring(0, mismatchAt + 1 >=
words[i].Length? words[i].Length : mismatchAt + 1)));
pairs.Add(new KeyValuePair<string, string>(words[i + 1],
words[i + 1].Substring(0, mismatchAt + 1>=
words[i+1].Length? words[i+1].Length : mismatchAt + 1)));
}
Dictionary<string, string> wordHashMap =
new Dictionary<string, string>();
foreach (var pair in pairs)
{
if (!wordHashMap.ContainsKey(pair.Key))
{
wordHashMap.Add(pair.Key, pair.Value);
}
else
{
if(wordHashMap[pair.Key].Length < pair.Value.Length)
wordHashMap[pair.Key] = pair.Value;
}
}
wordHashMap.Dump("Final Mapping");
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment