Share My 23ms Solution based on Merge Intervals


  • 0
    M

    This solution based on the problem: 56. Merge Intervals.

    1. Find all the substring of s that is in dict, and represents it as an interval [a, b], where a is the beginning index of the substring and b is the next of the end of substring. For example, s = "abcxyz123", "abc" is represented as [0, 3].

    2. Merge the above intervals. For example s = "abcxyz123" and dict = ["abc","123"], the merged intervals is [[0, 3], [6, 9]]

    3. Insert "<b>" and "<\b>" at the begin and end of each interval.

    class Solution {
    public:
        string addBoldTag(string s, vector<string>& dict) {
            vector<pair<int, int>> intervals;
            vector<pair<int, int>> res;
            
            // Find intervals
            for (string w : dict) {
                size_t pos = 0, next = 0;
                while ((pos = s.find(w, next)) != string::npos) {
                    intervals.push_back(make_pair((int)pos, (int)pos + w.size()));
                    next = pos + 1;
                }
            }
            
            // Merge intervals
            sort(intervals.begin(), intervals.end());
            for (int i = 0; i < intervals.size(); i++) {
                if (!res.empty() && intervals[i].first <= res.back().second) {
                    res.back().second = max(intervals[i].second, res.back().second);
                } else {
                    res.push_back(intervals[i]);
                }
            }
            
            // Insert tags
            int offset = 0;
            for (auto p : res) {
                s.insert(p.first + offset, "<b>");
                offset += 3;
                s.insert(p.second + offset, "</b>");
                offset += 4;
            }
            return s;
        }
    };
    

Log in to reply
 

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