TireNode solution


  • 0
    T
    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 = 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;
    }
    

  • 0
    A

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


  • 0
    T

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


  • 0
    T

    @actionlee0405 just update it


Log in to reply
 

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