# Trie and merge intervals

• Add all the words in the dictionary to a trie. Find the longest word in dictionary that can be found for substring s(x, s.Length) for each x < s.Length-1.

Once we have the longest valid portion of a substring. Start from 0 and try to expand the longest valid string such the current index x <= maxEnd found so far. Once we reach the end, add the interval to a list. Merge previous interval with current interval if the gap between them is just 1.

We now have a consolidated list of intervals that need to be surrounded by bold tags.

``````public class Solution {
class Trie {
public TrieNode Root;
public Trie(){
this.Root = new TrieNode(false);
}

{
TrieNode cur = this.Root;
for(int i = 0; i < word.Length; i++)
{
if (!cur.Next.ContainsKey(word[i]))
{
cur.Next[word[i]] = new TrieNode(false);
}

cur = cur.Next[word[i]];
}

cur.IsWord = true;
}

public int GetLongestMatch(string word, int startIdx)
{
TrieNode cur = this.Root;
int maxWord = -1;
int i = startIdx;
for(; i < word.Length; i++)
{
if (!cur.Next.ContainsKey(word[i]))
{
break;
}

if (cur.Next[word[i]].IsWord)
{
//Console.WriteLine("Found word {0}", i);
maxWord = i;
}

cur = cur.Next[word[i]];
}

return maxWord;
}
}

class TrieNode
{
public bool IsWord;
public Dictionary<char,TrieNode> Next;
public TrieNode(bool isWord)
{
this.IsWord = isWord;
this.Next = new Dictionary<char,TrieNode>();
}
}

public string AddBoldTag(string s, string[] dict) {
Trie t = new Trie();
foreach(var dw in dict)
{
}

int[] maxLenMatch = new int[s.Length];

for(int start = 0; start < s.Length; start++)
{
int end = t.GetLongestMatch(s, start);
maxLenMatch[start] = end;
}

List<Tuple<int,int>> bTags = new List<Tuple<int,int>>();
int curStart = 0;
int curEnd = maxLenMatch[0];
while(curStart < s.Length)
{
if (curEnd == -1)
{
while(curStart < s.Length && maxLenMatch[curStart] == -1)
{
curStart++;
}

if (curStart < s.Length)
{
curEnd = maxLenMatch[curStart];
}
}
else {
int i = curStart;
while(i < s.Length && i <= curEnd)
{
curEnd = Math.Max(curEnd, maxLenMatch[i]);
i++;
}

// we have stretched curEnd as much as we can.
var prev = bTags.LastOrDefault();
if (prev != null && prev.Item2 + 1 == curStart)
{
bTags.RemoveAt(bTags.Count()-1);

}
else {
}

curStart = curEnd + 1;
curEnd = -1;
}
}

StringBuilder b = new StringBuilder();
int parsedIdx = 0;
if (!bTags.Any())
{
return s;
}

foreach(var bt in bTags)
{
b.Append(s.Substring(parsedIdx, bt.Item1-parsedIdx));
b.Append(@"<b>");
b.Append(s.Substring(bt.Item1, bt.Item2-bt.Item1+1));
b.Append(@"</b>");
parsedIdx = bt.Item2+1;
}

if (parsedIdx < s.Length)
{
b.Append(s.Substring(parsedIdx));
}

return b.ToString();

}
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.