{"id":7374,"date":"2020-09-13T01:39:31","date_gmt":"2020-09-13T08:39:31","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=7374"},"modified":"2020-09-13T20:04:54","modified_gmt":"2020-09-14T03:04:54","slug":"leetcode-1585-check-if-string-is-transformable-with-substring-sort-operations","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/string\/leetcode-1585-check-if-string-is-transformable-with-substring-sort-operations\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1585. Check If String Is Transformable With Substring Sort Operations"},"content":{"rendered":"\n<figure class=\"wp-block-embed-youtube wp-block-embed is-type-video is-provider-youtube wp-embed-aspect-16-9 wp-has-aspect-ratio\"><div class=\"wp-block-embed__wrapper\">\n<iframe loading=\"lazy\" title=\"\u82b1\u82b1\u9171 LeetCode 1585. Check If String Is Transformable With Substring Sort Operations - \u5237\u9898\u627e\u5de5\u4f5c EP356\" width=\"500\" height=\"281\" src=\"https:\/\/www.youtube.com\/embed\/Pkd3FampKBk?feature=oembed\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share\" referrerpolicy=\"strict-origin-when-cross-origin\" allowfullscreen><\/iframe>\n<\/div><\/figure>\n\n\n\n<p>Given two strings&nbsp;<code>s<\/code>&nbsp;and&nbsp;<code>t<\/code>, you want to transform string&nbsp;<code>s<\/code>&nbsp;into string&nbsp;<code>t<\/code>&nbsp;using the following&nbsp;operation any number of times:<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>Choose a&nbsp;<strong>non-empty<\/strong>&nbsp;substring in&nbsp;<code>s<\/code>&nbsp;and sort it in-place&nbsp;so the characters are in&nbsp;<strong>ascending order<\/strong>.<\/li><\/ul>\n\n\n\n<p>For example, applying the operation on the underlined substring in&nbsp;<code>\"14234\"<\/code>&nbsp;results in&nbsp;<code>\"12344\"<\/code>.<\/p>\n\n\n\n<p>Return&nbsp;<code>true<\/code>&nbsp;if&nbsp;<em>it is possible to transform string&nbsp;<code>s<\/code>&nbsp;into string&nbsp;<code>t<\/code><\/em>. Otherwise,&nbsp;return&nbsp;<code>false<\/code>.<\/p>\n\n\n\n<p>A&nbsp;<strong>substring<\/strong>&nbsp;is a contiguous sequence of characters within 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 = \"84532\", t = \"34852\"\n<strong>Output:<\/strong> true\n<strong>Explanation:<\/strong> You can transform s into t using the following sort operations:\n\"84532\" (from index 2 to 3) -&gt; \"84352\"\n\"84352\" (from index 0 to 2) -&gt; \"34852\"\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 = \"34521\", t = \"23415\"\n<strong>Output:<\/strong> true\n<strong>Explanation:<\/strong> You can transform s into t using the following sort operations:\n\"34521\" -&gt; \"23451\"\n\"23451\" -&gt; \"23415\"\n<\/pre>\n\n\n\n<p><strong>Example 3:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> s = \"12345\", t = \"12435\"\n<strong>Output:<\/strong> false\n<\/pre>\n\n\n\n<p><strong>Example 4:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> s = \"1\", t = \"2\"\n<strong>Output:<\/strong> false\n<\/pre>\n\n\n\n<p><strong>Constraints:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>s.length == t.length<\/code><\/li><li><code>1 &lt;= s.length &lt;= 10<sup>5<\/sup><\/code><\/li><li><code>s<\/code>&nbsp;and&nbsp;<code>t<\/code>&nbsp;only contain digits from&nbsp;<code>'0'<\/code>&nbsp;to&nbsp;<code>'9'<\/code>.<\/li><\/ul>\n\n\n\n<p><strong>Solution: Queue<\/strong><\/p>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"960\" height=\"540\" src=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/09\/1585-ep356-1.png\" alt=\"\" class=\"wp-image-7379\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/09\/1585-ep356-1.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/09\/1585-ep356-1-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/09\/1585-ep356-1-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/figure>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"960\" height=\"540\" src=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/09\/1585-ep356-2.png\" alt=\"\" class=\"wp-image-7380\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/09\/1585-ep356-2.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/09\/1585-ep356-2-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/09\/1585-ep356-2-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/figure>\n\n\n\n<p>We can move a smaller digit from right to left by sorting two adjacent digits. <br>e.g. 1857<strong>2<\/strong> -&gt; 185<strong>2<\/strong>7 -&gt; 18<strong>2<\/strong>57 -&gt; 1<strong>2<\/strong>857, but we can not move a larger to the left of a smaller one.<\/p>\n\n\n\n<p>Thus, for each digit in the target string, we find the first occurrence of it in s, and try to move it to the front by checking if there is any smaller one in front of it.<\/p>\n\n\n\n<p>Time complexity: O(n)<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++\">\nclass Solution {\npublic:\n  bool isTransformable(string s, string t) {\n    vector<deque<int>> idx(10);\n    for (int i = 0; i < s.length(); ++i)\n      idx[s[i] - '0'].push_back(i);\n    for (char c : t) {\n      const int d  = c - '0';\n      if (idx[d].empty()) return false;\n      for (int i = 0; i < d; ++i)\n        if (!idx[i].empty() &#038;&#038; idx[i].front() < idx[d].front())\n          return false;\n      idx[d].pop_front();      \n    }\n    return true;\n  }\n};\n<\/pre>\n\n<\/div><h2 class=\"tabtitle\">Python3<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"c++\">\nclass Solution:\n  def isTransformable(self, s: str, t: str) -> bool:\n    idx = defaultdict(deque)\n    for i, c in enumerate(s):\n      idx[int(c)].append(i)\n    for c in t:\n      d = int(c)\n      if not idx[d]: return False\n      for i in range(d):\n        if idx[i] and idx[i][0] < idx[d][0]: return False\n      idx[d].popleft()\n    return True\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>Given two strings&nbsp;s&nbsp;and&nbsp;t, you want to transform string&nbsp;s&nbsp;into string&nbsp;t&nbsp;using the following&nbsp;operation any number of times: Choose a&nbsp;non-empty&nbsp;substring in&nbsp;s&nbsp;and sort it in-place&nbsp;so the characters are in&nbsp;ascending&#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":[214,217,4,145],"class_list":["post-7374","post","type-post","status-publish","format-standard","hentry","category-string","tag-deque","tag-hard","tag-string","tag-transform","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7374","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=7374"}],"version-history":[{"count":4,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7374\/revisions"}],"predecessor-version":[{"id":7381,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7374\/revisions\/7381"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=7374"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=7374"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=7374"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}