616. Add Bold Tag in String

링크: https://leetcode.com/problems/add-bold-tag-in-string/

 

동일한 문제: https://leetcode.com/problems/bold-words-in-string/

Account Login - LeetCode

Input: s = "abcxyz123" dict = ["abc","123"]

Output: "<b>abc</b>xyz<b>123</b>"

 

 dict에 존재하는 문자열이 s에 존재한다면 "<b>, </b>"로 감싸서 return해주는 문제.  dict 안에 있는 문자열이 겹쳐서 존재하는 경우에는 겹치는 그대로 감싸준다.

 

class Solution {
public:
    string addBoldTag(string s, vector<string>& dict) {
        vector<int> marks(s.size(), 0);
        
        for(int i = 0; i < dict.size(); i++){
            string target = dict[i];
            int idx = s.find(target);
            while(idx != -1){
                for(int j = idx; j < idx + target.size(); j++){
                    marks[j]++;
                }
                idx = s.find(target, idx + 1);
            }
        }
        
        int left = 0;
        int right = 0;
        
        string ans = "";
        string tmp = "";
        
        while(left <= right && right < marks.size()){
            if(marks[right] > 0){
                tmp += s[right];
                right++;
            } else {
                if(tmp == ""){
                    ans += s[right];
                } else {
                    ans += "<b>" + tmp + "</b>";
                    tmp = "";
                    ans += s[right];
                }
                left = right + 1;
                right = right + 1;
            }
        }
        
        if(tmp != ""){
            ans += "<b>" + tmp + "</b>";
        }
        
        return ans;
    }
};

 string을 find할때 시작점을 정해준다.  string s = "abcxyxabc"라고 한다면 s.find("abc", 0)로 가져가면 리턴값이 0이 출력된다.  0은 abc가 시작되는 인덱스 값이다.  만일 s.find("abc", 2)를 수행한 경우는 두 번째 "abc" 문자열 시작점인 6이 출력된다.  

 find를 사용할 기회가 없어서 떠오르지 않았는데, 본 문제로 바로바로 나올 수 있도록 기억해둔다.