{"id":9223,"date":"2021-12-24T01:13:39","date_gmt":"2021-12-24T09:13:39","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=9223"},"modified":"2021-12-24T01:13:44","modified_gmt":"2021-12-24T09:13:44","slug":"leetcode-1910-remove-all-occurrences-of-a-substring","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/string\/leetcode-1910-remove-all-occurrences-of-a-substring\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1910. Remove All Occurrences of a Substring"},"content":{"rendered":"\n<p>Given two strings&nbsp;<code>s<\/code>&nbsp;and&nbsp;<code>part<\/code>, perform the following operation on&nbsp;<code>s<\/code>&nbsp;until&nbsp;<strong>all<\/strong>&nbsp;occurrences of the substring&nbsp;<code>part<\/code>&nbsp;are removed:<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>Find the&nbsp;<strong>leftmost<\/strong>&nbsp;occurrence of the substring&nbsp;<code>part<\/code>&nbsp;and&nbsp;<strong>remove<\/strong>&nbsp;it from&nbsp;<code>s<\/code>.<\/li><\/ul>\n\n\n\n<p>Return&nbsp;<code>s<\/code><em>&nbsp;after removing all occurrences of&nbsp;<\/em><code>part<\/code>.<\/p>\n\n\n\n<p>A&nbsp;<strong>substring<\/strong>&nbsp;is a contiguous sequence of characters in a string.<\/p>\n\n\n\n<p><strong>Example 1:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> s = \"daabcbaabcbc\", part = \"abc\"\n<strong>Output:<\/strong> \"dab\"\n<strong>Explanation<\/strong>: The following operations are done:\n- s = \"da<strong><u>abc<\/u><\/strong>baabcbc\", remove \"abc\" starting at index 2, so s = \"dabaabcbc\".\n- s = \"daba<strong><u>abc<\/u><\/strong>bc\", remove \"abc\" starting at index 4, so s = \"dababc\".\n- s = \"dab<strong><u>abc<\/u><\/strong>\", remove \"abc\" starting at index 3, so s = \"dab\".\nNow s has no occurrences of \"abc\".\n<\/pre>\n\n\n\n<p><strong>Example 2:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> s = \"axxxxyyyyb\", part = \"xy\"\n<strong>Output:<\/strong> \"ab\"\n<strong>Explanation<\/strong>: The following operations are done:\n- s = \"axxx<strong><u>xy<\/u><\/strong>yyyb\", remove \"xy\" starting at index 4 so s = \"axxxyyyb\".\n- s = \"axx<strong><u>xy<\/u><\/strong>yyb\", remove \"xy\" starting at index 3 so s = \"axxyyb\".\n- s = \"ax<strong><u>xy<\/u><\/strong>yb\", remove \"xy\" starting at index 2 so s = \"axyb\".\n- s = \"a<strong><u>xy<\/u><\/strong>b\", remove \"xy\" starting at index 1 so s = \"ab\".\nNow s has no occurrences of \"xy\".\n<\/pre>\n\n\n\n<p><strong>Constraints:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>1 &lt;= s.length &lt;= 1000<\/code><\/li><li><code>1 &lt;= part.length &lt;= 1000<\/code><\/li><li><code>s<\/code>\u200b\u200b\u200b\u200b\u200b\u200b and&nbsp;<code>part<\/code>&nbsp;consists of lowercase English letters.<\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution: Simulation<\/strong><\/h2>\n\n\n\n<p>Time complexity: O(n<sup>2<\/sup>\/m)<br>Space complexity: O(n)<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"c++\">\/\/ Author: Huahua\nclass Solution {\npublic:\n  string removeOccurrences(string s, string part) {    \n    while (true) {\n      size_t i = s.find(part);\n      if (i == string::npos) break;\n      s.erase(i, part.size());      \n    }\n    return s;\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>Given two strings&nbsp;s&nbsp;and&nbsp;part, perform the following operation on&nbsp;s&nbsp;until&nbsp;all&nbsp;occurrences of the substring&nbsp;part&nbsp;are removed: Find the&nbsp;leftmost&nbsp;occurrence of the substring&nbsp;part&nbsp;and&nbsp;remove&nbsp;it from&nbsp;s. Return&nbsp;s&nbsp;after removing all occurrences of&nbsp;part. A&nbsp;substring&nbsp;is a&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[47],"tags":[177,179,4],"class_list":["post-9223","post","type-post","status-publish","format-standard","hentry","category-string","tag-medium","tag-simulation","tag-string","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9223","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=9223"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9223\/revisions"}],"predecessor-version":[{"id":9225,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9223\/revisions\/9225"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=9223"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=9223"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=9223"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}