Skip to content

Instantly share code, notes, and snippets.

@jianminchen
Created February 12, 2017 20:07
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save jianminchen/cf95a4da4a49ccb269bead2b90d6b9a1 to your computer and use it in GitHub Desktop.
Save jianminchen/cf95a4da4a49ccb269bead2b90d6b9a1 to your computer and use it in GitHub Desktop.
Prefix neighbors - study code
using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
class Solution {
class Index
{
public Dictionary<char, Index> Children { get; set; }
public bool IsWord { get; set; }
public string Word { get; set; }
public Index()
{
Children = new Dictionary<char, Index>();
IsWord = false;
Word = "";
}
public Tuple<string, string> Add(int index, char[] word, string wordy, string neighbour)
{
if (index == word.Length)
{
IsWord = true;
Word = wordy;
return new Tuple<string, string>(wordy, neighbour);
}
else
{
if (!Children.ContainsKey(word[index]))
{
Children[word[index]] = new Index();
}
return Children[word[index]].Add(index + 1, word, wordy, IsWord ? Word : neighbour);
}
}
}
static long Process(string[] dict)
{
var points = 0L;
var banned = new HashSet<string>();
var stack = new Stack<Tuple<string, string>>();
var index = new Index();
var groupped = dict.GroupBy(x => x[0]);
foreach(var g in groupped)
{
var sort = g.OrderBy(x => x.Length);
index = new Index();
stack = new Stack<Tuple<string, string>>();
banned = new HashSet<string>();
foreach(var word in sort)
{
stack.Push(index.Add(0, word.ToCharArray(), word, ""));
}
foreach (var tuple in stack)
{
if(!banned.Contains(tuple.Item1))
{
points += tuple.Item1.ToCharArray().Aggregate(0L, (val, next) => val + (long)next);
banned.Add(tuple.Item2);
}
}
}
return points;
}
static void Main(String[] args)
{
var n = Convert.ToInt32(Console.ReadLine());
var dict = Console.ReadLine().Split(' ');
var points = Process(dict);
Console.WriteLine(points);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment