Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
HackerRank - The hidden message - study code
using System;
using System.Collections.Generic;
using System.IO;
public class ResultInfo
{
public int Start { get; set; }
public string Word { get; set; }
}
public class TrieNode
{
public int Words { get; private set; }
public int Prefixes { get; private set; }
TrieNode[] edges;
public string Word { get; private set; }
public void Add(string word, int start)
{
TrieNode node = this;
while (start < word.Length)
{
node.Prefixes++;
int index = word[start] - 'a';
if(node.edges == null)
node.edges = new TrieNode[26];
if (node.edges[index] == null)
{
node.edges[index] = new TrieNode();
}
node = node.edges[index];
start++;
}
node.Words++;
node.Prefixes++;
node.Word = word;
}
public List<ResultInfo> FindWords(string s)
{
List<ResultInfo> result = new List<ResultInfo>();
List<string> matches = new List<string>();
for (int i = 0; i < s.Length; i++)
{
int count = result.Count;
FindMatch(s, i, matches);
for (int j = count; j < matches.Count; j++)
{
result.Add(new ResultInfo {Start = i, Word = matches[j]});
}
}
return result;
}
void FindMatch(string s, int i, List<string> matches)
{
var node = this;
while (i < s.Length)
{
if (node.Word != null)
matches.Add(node.Word);
int index = s[i] - 'a';
if (node.edges == null || node.edges[index] == null)
{
return;
}
node = node.edges[index];
i++;
}
if(node.Word != null)
matches.Add(node.Word);
}
}
class Solution {
static void Main(String[] args) {
string t = Console.ReadLine();
string p = Console.ReadLine();
string[] phrase = p.Split(' ');
TrieNode root = new TrieNode();
foreach (string word in phrase)
{
root.Add(word, 0);
}
List<ResultInfo> matches = root.FindWords(t);
Dictionary<string, List<int>> d = new Dictionary<string, List<int>>();
foreach (var resultInfo in matches)
{
if (d.ContainsKey(resultInfo.Word))
{
d[resultInfo.Word].Add(resultInfo.Start);
}
else
{
var l = new List<int> {resultInfo.Start};
d.Add(resultInfo.Word, l);
}
}
int[] phraseMatch = new int[phrase.Length];
for (int i = 0; i < phraseMatch.Length; i++)
{
phraseMatch[i] = -1;
}
int matchesCount = 0;
int lastIndex = -1;
for (int i = 0; i < phrase.Length; i++)
{
string word = phrase[i];
if (d.ContainsKey(word))
{
var l = d[word];
bool found = false;
for (int j = 0; j < l.Count; j++)
{
if (l[j] > lastIndex)
{
lastIndex = l[j];
phraseMatch[i] = lastIndex;
matchesCount++;
found = true;
break;
}
}
if (found == false)
{
break;
}
}
else
{
break;
}
}
if (matchesCount == phrase.Length)
{
Console.WriteLine("YES");
PrintMatches(phrase, phraseMatch);
Console.WriteLine(LevenshteinDistance(t, p));
}
else
{
Console.WriteLine("NO");
if (matchesCount == 0)
{
Console.WriteLine("0");
}
else
{
PrintMatches(phrase, phraseMatch);
}
Console.WriteLine("0");
}
}
static int LevenshteinDistance(string s, string t)
{
if (s == t) return 0;
if (s.Length == 0) return t.Length;
if (t.Length == 0) return s.Length;
int[] v0 = new int[t.Length + 1];
int[] v1 = new int[t.Length + 1];
for (int i = 0; i < v0.Length; i++)
v0[i] = i;
for (int i = 0; i < s.Length; i++)
{
v1[0] = i + 1;
for (int j = 0; j < t.Length; j++)
{
var cost = (s[i] == t[j]) ? 0 : 2;
v1[j + 1] = Math.Min(v1[j] + 1, Math.Min(v0[j + 1] + 1, v0[j] + cost));
}
for (int j = 0; j < v0.Length; j++)
v0[j] = v1[j];
}
return v1[t.Length];
}
static void PrintMatches(string[] phrase, int[] phraseMatch)
{
bool first = true;
for (int i = 0; i < phraseMatch.Length; i++)
{
if (phraseMatch[i] >= 0)
{
Console.Write("{0}{1} {2} {3}", first ? "" : " ", phrase[i], phraseMatch[i],
phraseMatch[i] + phrase[i].Length - 1);
first = false;
}
}
Console.WriteLine();
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.