C++ O(n^2) solution

  • 0
        string addBoldTag(string s, vector<string>& dict) {
            unordered_set<string> d;
            vector<pair<int, int>> sub;
            for(int i=0;i<dict.size();i++) d.insert(dict[i]);
            for(int i=0;i<s.size();i++) {
                string temp;
                for(int j=i;j<s.size();j++) {
                    temp.append(1, s[j]);
                    if(d.find(temp)!=d.end()) sub.push_back(make_pair(i, j));
            if(sub.size()==0) return s;
            vector<pair<int, int>> res(1, sub[0]);
            sort(sub.begin(), sub.end(), comp);
            for(int i=1;i<sub.size();i++) {
                int cur=res.size()-1;
                if(sub[i].first>res[cur].second+1) res.push_back(sub[i]);
                else if(sub[i].second>res[cur].second) res[cur].second=sub[i].second;
            int add=0;
            for(int i=0;i<res.size();i++) {
                string a=s.substr(0, res[i].first+add), b=s.substr(res[i].first+add, res[i].second-res[i].first+1), c="";
                if(res[i].second<s.size()-add-1) c=s.substr(res[i].second+1+add);
            return s;
        static bool comp(pair<int, int>& p1, pair<int, int>& p2) {
            return p1.first<p2.first;

Log in to reply

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