[616. Add Bold Tag in String] Two different method: Merge Interval or Using Vector


  • 0

    Using vector: Each time we use one word from our dict, and match it with our string s.
    This method is much more faster.

    class Solution {
    public:
    string addBoldTag(string s, vector<string>& dict) {
        if(s.empty() || dict.empty()) return s;
        vector<bool> check(s.size(), false);
        for(auto d : dict){
            int len = d.size();
            for(int i = 0; i + len - 1< s.size(); ++i){
                int j = i + len - 1;
                string tmp = s.substr(i, len);
                if(tmp == d){
                    while(j >= i){check[j--] = true;}
                }
            }
        }
        string res = "";
        int i = 0;
        while(i < s.size()){
            if(check[i]){
                res += "<b>";
                while(i < s.size() && check[i]){
                    res += s[i++];
                }
                res += "</b>";
            }else{
                res += s[i++];
            }
        }
        return res;
    }
    };
    

    Merge interval: Using unordered_set.

    //200ms, each time we create a new substring from s, and match it with our dict.

     class Solution {
     public:
    string addBoldTag(string s, vector<string>& dict) {
        if(s.empty() || dict.empty()) return s;
        unordered_set<string> st;
        int len = 0;
        for(auto ss : dict){
            st.insert(ss);
            len = len < ss.size() ? ss.size() : len;
        }
        string res = "";
        int pre_start = 0;
        pair<int,int> intvl = {0,-1};
        int e = 0;// the largest index of effective substring
        for(int i = 0; i < s.size(); ++i){
            pair<int,int> new_intvl = {i,-1};
            int cur = max(e, i);// the ending of our current substring
            while(cur < s.size()){
                if(cur - i + 1 > len) break;
                //substring length is larger than the max length of word in the dict.
                string tmp = s.substr(i, cur - i + 1);
                if(st.find(tmp) != st.end()){
                    new_intvl.second = cur;
                }
                cur++;
            }
            if(new_intvl.second == -1) continue;
            e = new_intvl.second;//Update the largest effective index of substring
            if(intvl.second + 1 >= new_intvl.first){
                intvl.second = new_intvl.second;
            }else{
                if(intvl.second - intvl.first + 1) res += s.substr(pre_start, intvl.first - pre_start) + "<b>" + s.substr(intvl.first, intvl.second - intvl.first + 1) + "</b>";
                pre_start = intvl.second + 1;
                intvl = new_intvl;
            }
        }
         
        //check whether there is still some substring needed to be added to our result.
        if(pre_start < s.size()){
            if(intvl.second - intvl.first + 1) res += s.substr(pre_start, intvl.first - pre_start) + "<b>" + s.substr(intvl.first, intvl.second - intvl.first + 1) + "</b>";
            pre_start = intvl.second + 1;
            if(pre_start < s.size()){
                res += s.substr(pre_start);
            }
        }
        return res;
    }
    };

Log in to reply
 

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