A simple c++ solution (96 ms, beat 100%)


  • 0
    Z

    The method is quite simple. In the code, we search the dictionary to match the longest sub-string of string "s" with the start index "start". The variable "end" means the last index of "s" that have been processed and put into the result. If there is no substr (with the start index "start") in the dictionary and start == end + 1, it means s.substr(start, 1) is not in the bold tag.

    string addBoldTag(string s, vector<string>& dict) {
            string res;
            int start = 0, end = -1;
            bool in = false;
            while (start <= s.length()) {
                for (int i = 0; i < dict.size(); i++) {
                    if (dict[i] == s.substr(start, dict[i].length())) {
                        int j = start + dict[i].length() - 1;
                        if (in == false) {
                            res += "<b>";
                            in = true;
                        }
                        if (j > end) {
                            res += s.substr(end + 1, j - end);
                            end = j;
                        }
                    }
                }
                if (start == end + 1) {
                    if (in) {
                        res += "</b>";
                        in = false;
                    }
                    if (start < s.length()) res += s.substr(start, 1);
                    end = start;
                }
                start++;
            }
            return res;
        }
    

Log in to reply
 

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