Trie and merge intervals


  • 0

    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);
            }
            
            public void AddWord(string word)
            {
                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)
            {
                t.AddWord(dw);
            }
            
            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);
                        bTags.Add(new Tuple<int,int>(prev.Item1, curEnd));
        
                    }
                    else {
                        bTags.Add(new Tuple<int,int>(curStart, curEnd));    
                    }
                    
                    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();
            
        }
    }
    

Log in to reply
 

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