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 is followed by another letter and no digit is followed by another digit. That is, no two adjacent characters have the same type.
Return the reformatted string or return an empty string if it is impossible to reformat the string.
Example 1:
Input: s = "a0b1c2" Output: "0a1b2c" Explanation: No two adjacent characters have the same type in "0a1b2c". "a0b1c2", "0a1b2c", "0c2a1b" are also valid permutations.
Example 2:
Input: s = "leetcode" Output: "" Explanation: "leetcode" has only characters so we cannot separate them by digits.
Example 3:
Input: s = "1229857369" Output: "" Explanation: "1229857369" has only digits so we cannot separate them by characters.
Example 4:
Input: s = "covid2019" Output: "c2o0v1i9d"
Example 5:
Input: s = "ab123" Output: "1a2b3"
Constraints:
1 <= s.length <= 500
s
consists of only lowercase English letters and/or digits.
Solution: Two streams
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.
Time complexity: O(n)
Space complexity: O(n)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
// Author: Huahua class Solution { public: string reformat(string s) { string q1; string q2; for (char c : s) { if (isalpha(c)) q1 += c; else q2 += c; } if (q1.length() < q2.length()) swap(q1, q2); if (q1.length() > q2.length() + 1) return ""; string ans; while (!q1.empty()) { ans += q1.back(); q1.pop_back(); if (q2.empty()) break; ans += q2.back(); q2.pop_back(); } return ans; } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment