{"id":6643,"date":"2020-04-20T00:13:16","date_gmt":"2020-04-20T07:13:16","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=6643"},"modified":"2020-04-20T00:18:54","modified_gmt":"2020-04-20T07:18:54","slug":"leetcode-1417-reformat-the-string","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/string\/leetcode-1417-reformat-the-string\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1417. Reformat The String"},"content":{"rendered":"\n

Given alphanumeric string s<\/code>. (Alphanumeric string<\/strong> is a string consisting of lowercase English letters and digits).<\/p>\n\n\n\n

You have to find a permutation of the string where no letter is followed by another letter and no digit is followed by another digit. That is, no two adjacent characters have the same type.<\/p>\n\n\n\n

Return the reformatted string<\/em> or return an empty string<\/strong> if it is impossible to reformat the string.<\/p>\n\n\n\n

Example 1:<\/strong><\/p>\n\n\n\n

Input:<\/strong> s = \"a0b1c2\"\nOutput:<\/strong> \"0a1b2c\"\nExplanation:<\/strong> No two adjacent characters have the same type in \"0a1b2c\". \"a0b1c2\", \"0a1b2c\", \"0c2a1b\" are also valid permutations.\n<\/pre>\n\n\n\n
Example 2:<\/strong><\/p>\n\n\n\n
Input:<\/strong> s = \"leetcode\"\nOutput:<\/strong> \"\"\nExplanation:<\/strong> \"leetcode\" has only characters so we cannot separate them by digits.\n<\/pre>\n\n\n\n
Example 3:<\/strong><\/p>\n\n\n\n
Input:<\/strong> s = \"1229857369\"\nOutput:<\/strong> \"\"\nExplanation:<\/strong> \"1229857369\" has only digits so we cannot separate them by characters.\n<\/pre>\n\n\n\n
Example 4:<\/strong><\/p>\n\n\n\n
Input:<\/strong> s = \"covid2019\"\nOutput:<\/strong> \"c2o0v1i9d\"\n<\/pre>\n\n\n\n
Example 5:<\/strong><\/p>\n\n\n\n
Input:<\/strong> s = \"ab123\"\nOutput:<\/strong> \"1a2b3\"\n<\/pre>\n\n\n\n
Constraints:<\/strong><\/p>\n\n\n\n
  • 1 <= s.length <= 500<\/code><\/li>
  • s<\/code> consists of only lowercase English letters and\/or digits.<\/li><\/ul>\n\n\n\n
    Solution: Two streams<\/strong><\/h2>\n\n\n\n
    Create two stacks, one for alphas, another for numbers. If the larger stack has more than one element than the other one then no solution, return “”. Otherwise, interleave two stacks, start with the larger one.<\/p>\n\n\n\n
    Time complexity: O(n)
    Space complexity: O(n)<\/p>\n\n\n\n
    \n
    C++<\/h2>\n
    \n\n
    \n\/\/ Author: Huahua\nclass Solution {\npublic:\n  string reformat(string s) {\n    string q1;\n    string q2;\n    for (char c : s) {\n      if (isalpha(c))\n        q1 += c;\n      else\n        q2 += c;\n    }    \n    if (q1.length() < q2.length())\n      swap(q1, q2);\n    if (q1.length() > q2.length() + 1) \n      return \"\";\n    string ans;\n    while (!q1.empty()) {\n      ans += q1.back();\n      q1.pop_back();\n      if (q2.empty()) break;\n      ans += q2.back();\n      q2.pop_back();\n    }\n    return ans;\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"
    Given alphanumeric string s. (Alphanumeric string is a string consisting of lowercase English letters and digits). You have to find a permutation of the string where no letter…<\/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":[222,365,213,180,4],"class_list":["post-6643","post","type-post","status-publish","format-standard","hentry","category-string","tag-easy","tag-interleaving","tag-queue","tag-stack","tag-string","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6643","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=6643"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6643\/revisions"}],"predecessor-version":[{"id":6645,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6643\/revisions\/6645"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=6643"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=6643"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=6643"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}