28ms C++ Solution using HashMap


  • 0
    int searchMaxLen(string& s, int start, vector<string> words)
    {
        int len = 0;
        for(string w : words)
        {
            int wl = w.length();
            if(start+wl<=s.length() && s.substr(start, wl)==w)
                len = max(len, wl);
        }
        return len;
    }
    
    string addBoldTag(string s, vector<string>& dict) {
        unordered_map<char, vector<string>> wdict;
        for(string word : dict)
        {
            wdict[word[0]].push_back(word);
        }
        
        for(int i=0; i<s.length(); ++i)
        {
            if(wdict.count(s[i]) == 0) continue;
            int len = searchMaxLen(s, i, wdict[s[i]]);
            if(len == 0) continue;
            for(int j=i+1; j<=i+len; ++j)
            {
                int curLen = searchMaxLen(s, j, wdict[s[j]]);
                len = max(len, j-i + curLen);
            }
            s.insert(i+len, "</b>");
            s.insert(i, "<b>");
            i += len+7;
        }
        return s;
    }
    

Log in to reply
 

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