# TireNode solution

• ``````public class Solution {
public string AddBoldTag(string s, string[] dict) {
TireNode root = new TireNode();

foreach(var word in dict){
var current = root;
foreach(var c in word){
if(!current.children.ContainsKey(c))

current = current.children[c];
}
current.isWord = true;
}

var dp = new bool[s.Length];
int len = s.Length;
for(int i = 0;i<len;i++){
var current = root;
int j = i;
while(j < len && current.children.ContainsKey(s[j])){
current = current.children[s[j]];
j++;
}

if(current.isWord){
for(int k = i;k<j;k++){
dp[k] = true;
}
}
}

var result = s.ToCharArray().Select(x=>x+"").ToList();
bool p = false;
for(int i = len-1;i>=0;i--){
if(dp[i] && !p){
result.Insert(i+1,"</b>");
}

if(dp[i] && (i == 0 || !dp[i-1])){
result.Insert(i,"<b>");
}
p = dp[i];
}

return string.Join("",result);
}
}

public class TireNode{
public Dictionary<char,TireNode> children = new Dictionary<char,TireNode>();
public bool isWord = false;
}
``````

• @tangalai said in TireNode solution:

public class Solution {
public string AddBoldTag(string s, string[] dict) {
TireNode root = new TireNode();

``````    foreach(var word in dict){
var current = root;
foreach(var c in word){
if(current.children[(int)c] == null)
current.children[(int)c] = new TireNode();

current = current.children[(int)c];
}
}

var dp = new bool[s.Length];
int len = s.Length;
for(int i = 0;i<len;i++){
var current = root;
int j = i;
while(j < len && current.children[(int)s[j]] != null){
dp[j] = true;
current = current.children[(int)s[j]];
j++;
//Console.WriteLine(current == null);
}
}

var result = s.ToCharArray().Select(x=>x+"").ToList();
bool p = false;
``````

When you mark the dp array, it seems you don't check if a trie node is the end of a word in the dict but simply assign dp[j] = true. What happen for s = "abe123xyz", dict = ["abc", "xyz"]? I think your output will be "abexyz123" which is wrong.

• @actionlee0405 Yes, that's why I was failed at first time. Looks like I copied the wrong solution.

• @actionlee0405 just update it

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