Short C++ solutions, Counting pair and counting bold


  • 0
    Z

    counting pair

    class Solution {
    public:
        string addBoldTag(string s, vector<string>& dict) {
            int n = s.size();
            vector<int> open(n + 1), closed(n + 1);
            for ( string & w : dict ) {
                int i = -1;
                while ( (i = s.find(w, i + 1)) != string::npos ) {
                    ++open[i];
                    ++closed[i + w.size()];
                }
            }
            string tagged;
            int pre = 0;
            for ( int i = 0, t = 0; i <= n; ++i ) {
                if ( open[i] && 0 == t && ! closed[i] ) {
                    tagged += s.substr(pre, i - pre) + "<b>";
                    pre = i;
                }
                t += open[i];
                t -= closed[i];
                if ( closed[i] && 0 == t && ! open[i] ) {
                    tagged += s.substr(pre, i - pre) + "</b>";
                    pre = i;
                }
            }
            return tagged + s.substr(pre);
        }
    };
    
    // 70 / 70 test cases passed.
    // Status: Accepted
    // Runtime: 23 ms
    

    counting bold

    class Solution {
    public:
        string addBoldTag(string s, vector<string>& dict) {
            vector<bool> bold(s.size() + 2);
            vector<string> sdict(dict);
            auto cmp = [] (string & a, string & b) { return a.size() > b.size(); };
            sort(sdict.begin(), sdict.end(), cmp);
            for ( int i = 0, j; i < s.size(); ++i ) {
                for ( j = 0; j < sdict.size(); ++j )
                    if ( s.find(sdict[j], i) == i )
                        break;
                if ( j < sdict.size() )
                    fill(bold.begin() + i + 1, bold.begin() + i + 1 + sdict[j].size(), true);
            }
            string t;
            for ( int i = 1; i <= s.size(); ++i ) {
                if ( ! bold[i-1] && bold[i] ) t += "<b>";
                t += s[i-1];
                if ( bold[i] && ! bold[i+1] ) t += "</b>";
            }
            return t;
        }
    };
    
    // 70 / 70 test cases passed.
    // Status: Accepted
    // Runtime: 292 ms
    

Log in to reply
 

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