leetcode-1417-easy

Reformat The String

You are given an 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.
Constraints:

1 <= s.length <= 500
s consists of only lowercase English letters and/or digits.

思路一：数字和字母分别存储，如果是合法的字符串，他们的差值 <= 1。拼接新字符串时，按间隔拼接即可

public String reformat(String s) {
    char[] chars = s.toCharArray();

    Deque<Character> digits = new ArrayDeque<>();
    Deque<Character> letters = new ArrayDeque<>();

    for (char c : chars) {
        if (isLetter(c)) letters.add(c);
        else digits.add(c);
    }

    if (Math.abs(digits.size() - letters.size()) > 1) return s;

    StringBuilder sb = new StringBuilder();
    int min = Math.min(digits.size(), letters.size());
    for (int i = 0; i < min; i++) {
        sb.append(digits.pop()).append(letters.pop());
    }

    if (!digits.isEmpty()) {
        sb.append(digits.pop());
    }

    if (!letters.isEmpty()) {
        sb.insert(0, letters.pop());
    }

    return sb.toString();
}

private static boolean isLetter(char c) {
    return c >= 'a' && c <= 'z';
}

思路二：看了一下题解，可以在原字符串上做双指针交换字符串，效率和空间会好很多