{"id":2914,"date":"2018-06-11T22:52:36","date_gmt":"2018-06-12T05:52:36","guid":{"rendered":"http:\/\/zxi.mytechroad.com\/blog\/?p=2914"},"modified":"2018-06-17T23:18:39","modified_gmt":"2018-06-18T06:18:39","slug":"leetcode-848-shifting-letters","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/string\/leetcode-848-shifting-letters\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 848. Shifting Letters"},"content":{"rendered":"<p><iframe loading=\"lazy\" title=\"\u82b1\u82b1\u9171 LeetCode 848. Shifting Letters - \u5237\u9898\u627e\u5de5\u4f5c EP196\" width=\"500\" height=\"375\" src=\"https:\/\/www.youtube.com\/embed\/gOycoA8pOqg?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><\/p>\n<h1><strong>Problem<\/strong><\/h1>\n<p>We have a string\u00a0<code>S<\/code>\u00a0of lowercase letters, and an integer array\u00a0<code>shifts<\/code>.<\/p>\n<p>Call the\u00a0<em>shift<\/em>\u00a0of a letter, the next letter in the alphabet, (wrapping around so that\u00a0<code>'z'<\/code>\u00a0becomes\u00a0<code>'a'<\/code>).<\/p>\n<p>For example,\u00a0<code>shift('a') = 'b'<\/code>,\u00a0<code>shift('t') = 'u'<\/code>, and\u00a0<code>shift('z') = 'a'<\/code>.<\/p>\n<p>Now for each\u00a0<code>shifts[i] = x<\/code>, we want to shift the first\u00a0<code>i+1<\/code>\u00a0letters of\u00a0<code>S<\/code>,\u00a0<code>x<\/code>\u00a0times.<\/p>\n<p>Return the final string\u00a0after all such shifts to\u00a0<code>S<\/code>\u00a0are applied.<\/p>\n<p><strong>Example 1:<\/strong><\/p>\n<pre class=\"crayon:false\"><strong>Input: <\/strong>S = \"abc\", shifts = [3,5,9]\r\n<strong>Output: <\/strong>\"rpl\"\r\n<strong>Explanation: <\/strong>\r\nWe start with \"abc\".\r\nAfter shifting the first 1 letters of S by 3, we have \"dbc\".\r\nAfter shifting the first 2 letters of S by 5, we have \"igc\".\r\nAfter shifting the first 3 letters of S by 9, we have \"rpl\", the answer.\r\n<\/pre>\n<p><strong>Note:<\/strong><\/p>\n<ol>\n<li><code>1 &lt;= S.length = shifts.length &lt;= 20000<\/code><\/li>\n<li><code>0 &lt;= shifts[i] &lt;= 10 ^ 9<\/code><\/li>\n<\/ol>\n<h1><strong>Solution<\/strong><\/h1>\n<p>Time complexity: O(n)<\/p>\n<p>Space complexity: O(1)<\/p>\n<p>C++<\/p>\n<pre class=\"lang:default decode:true \">\/\/ Author: Huahua\r\n\/\/ Running time: 54 ms\r\nclass Solution {\r\npublic:\r\n  string shiftingLetters(string S, vector&lt;int&gt;&amp; shifts) {\r\n    int c = 0;\r\n    for (int i = shifts.size() - 1; i &gt;= 0; --i) {\r\n      c += (shifts[i] % 26);\r\n      S[i] = (S[i] - 'a' + c) % 26 + 'a';\r\n    }          \r\n    return S;\r\n  }\r\n};<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>Problem We have a string\u00a0S\u00a0of lowercase letters, and an integer array\u00a0shifts. Call the\u00a0shift\u00a0of a letter, the next letter in the alphabet, (wrapping around so that\u00a0&#8216;z&#8217;\u00a0becomes\u00a0&#8216;a&#8217;).&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[49,47],"tags":[177,309,4],"class_list":["post-2914","post","type-post","status-publish","format-standard","hentry","category-math","category-string","tag-medium","tag-shift","tag-string","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/2914","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=2914"}],"version-history":[{"count":5,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/2914\/revisions"}],"predecessor-version":[{"id":2925,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/2914\/revisions\/2925"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=2914"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=2914"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=2914"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}