19ms One-pass C++ solution with classify and sort


  • 3
    Y

    Classify dict elements by first character and sort them by length first.
    One pass, match dict elements start with current character in descending order by length.
    Use left and right to store current bold interval, use _left to store the left end of current not bold interval.

    class Solution {
    public:
        string addBoldTag(string s, vector<string>& dict) {
            vector<pair<int,int>> d[128];
            int len = dict.size(), cur, goal;
            int sl = s.size();
            for (int i = 0 ; i < len; ++i){
                d[dict[i][0]].push_back({dict[i].size(),i});
            }
            for (int i = 0; i < 128; ++i){
                sort(d[i].begin(),d[i].end(),greater<pair<int,int>>());
            }
            int left = -1, right = -1, _left = 0;
            stringstream ans;
            for (int i = 0; i < sl; ++i){
                cur = 0;
                goal = right + 1 - i;
                for (auto & j : d[s[i]]){
                    if (left != -1 && j.first < goal)
                        break;
                    if (s.substr(i,j.first) == dict[j.second]){
                        cur = j.first;
                        break;
                    }
                }
                if (cur){
                    right = i + cur - 1;
                    if (left == -1){
                        left = i;
                        if (left > _left)
                            ans << s.substr(_left,left-_left);
                    }
                } else if (left != -1 && i > right){
                    _left = right + 1;
                    ans << "<b>";
                    ans << s.substr(left,right-left+1);
                    ans << "</b>";
                    left = -1;
                }
            }
            if (left != -1) {
                ans << "<b>";
                ans << s.substr(left);
                ans << "</b>";
            }
            else
                ans << s.substr(_left);
            return ans.str();
        }
    };
    

Log in to reply
 

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