Given an encoded string, return it’s decoded string.<\/p>\n\n\n\n
The encoding rule is: You may assume that the input string is always valid; No extra white spaces, square brackets are well-formed, etc.<\/p>\n\n\n\n Furthermore, you may assume that the original data does not contain any digits and that digits are only for those repeat numbers, k<\/em>. For example, there won’t be input like Examples:<\/strong><\/p>\n\n\n\n Time complexity: O(n^2) Given an encoded string, return it’s decoded string. The encoding rule is: k[encoded_string], where the encoded_string inside the square brackets is being repeated exactly k times. Note that k is guaranteed to…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[153],"tags":[177,17,180,4],"class_list":["post-5041","post","type-post","status-publish","format-standard","hentry","category-recursion","tag-medium","tag-recursion","tag-stack","tag-string","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/5041","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=5041"}],"version-history":[{"count":3,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/5041\/revisions"}],"predecessor-version":[{"id":5044,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/5041\/revisions\/5044"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=5041"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=5041"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=5041"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}k[encoded_string]<\/code>, where the encoded_string<\/em> inside the square brackets is being repeated exactly k<\/em> times. Note that k<\/em> is guaranteed to be a positive integer.<\/p>\n\n\n\n3a<\/code> or 2[4]<\/code>.<\/p>\n\n\n\ns = \"3[a]2[bc]\", return \"aaabcbc\".\ns = \"3[a2[c]]\", return \"accaccacc\".\ns = \"2[abc]3[cd]ef\", return \"abcabccdcdcdef\".<\/pre>\n\n\n\n
Solution 1: Recursion<\/strong><\/h2>\n\n\n\n
Space complexity: O(n)<\/p>\n\n\n\nC++<\/h2>\n
\n\/\/ Author: Huahua, 4ms\nclass Solution {\npublic:\n string decodeString(string s) {\n if (s.empty()) return \"\"; \n string ans;\n int i = 0;\n int n = s.length();\n int c = 0;\n while (isdigit(s[i]) && i < n) \n c = c * 10 + (s[i++] - '0');\n \n int j = i;\n if (i < n && s[i] == '[') { \n int open = 1;\n while (++j < n && open) {\n if (s[j] == '[') ++open;\n if (s[j] == ']') --open;\n }\n } else {\n while (j < n && isalpha(s[j])) ++j;\n } \n \n \/\/ \"def2[ac]\" => \"def\" + decodeString(\"2[ac]\")\n \/\/ | |\n \/\/ i j\n if (i == 0)\n return s.substr(0, j) + decodeString(s.substr(j));\n \n \/\/ \"3[a2[c]]ef\", ss = decodeString(\"a2[c]\") = \"acc\"\n \/\/ | |\n \/\/ i j\n string ss = decodeString(s.substr(i + 1, j - i - 2)); \n while (c--)\n ans += ss;\n \/\/ \"3[a2[c]]ef\", ans = \"abcabcabc\", ans += decodeString(\"ef\")\n ans += decodeString(s.substr(j));\n return ans;\n }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"