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.children.Add(c,new TireNode());
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 = len1;i>=0;i){
if(dp[i] && !p){
result.Insert(i+1,"</b>");
}
if(dp[i] && (i == 0  !dp[i1])){
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;
}
TireNode solution


@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.
