[LeetCode616]文字列に太字のタグを追加

Add Bold Tag String

文字列sと文字列dictのリストが与えられた場合、太字のタグの閉じたペアを追加する必要があります そして dictに存在するsの部分文字列をラップします。このような2つの部分文字列が重なっている場合は、閉じた太字タグの1つのペアだけでそれらをまとめる必要があります。また、太字のタグで囲まれた2つの部分文字列が連続している場合は、それらを組み合わせる必要があります。

例

Input: s = 'abcxyz123' dict = ['abc','123'] Output: ' abc xyz 123 ' Input: s = 'aaabbcc' dict = ['aaa','aab','bc'] Output: ' aaabbc c'

通知

指定されたdictには重複が含まれず、その長さは100を超えません。
入力内のすべての文字列の長さは[1、1000]の範囲です。

分析

この質問では、setを使用してすべての単語を保存できます。追加の配列isTagを使用して、sの各ビットを太字にする必要があるかどうかを記録します。次に、sの部分文字列を繰り返し処理します。部分文字列がdictで見つかった場合は、isTagに対応するビットをtrueに設定します。

トラバーサルでは、別のセットを使用してすべての単語の長さを記録できます。 dictで部分文字列を探すたびに、最も長い長さから検索を開始します。見つかった場合は、探す必要はありません。

この質問は、TrieTreeを使用して単語をdictに格納することでしたが、メモリがバーストすることがわかりました。したがって、最終的には、setとともに保存されます。

コード

class Solution { public: /** * @param s: a string * @param dict: a list of strings * @return: return a string */ string addBoldTag(string &s, vector &dict) { // write your code here int dictLen = dict.size() set words set lens int maxLen = 0 for(int i = 0 i

運用効率

あなたの提出物は39.17％の提出物を上回っています！