1417. 重新格式化字符串

题目描述：

给你一个混合了数字和字母的字符串 s，其中的字母均为小写英文字母。

请你将该字符串重新格式化，使得任意两个相邻字符的类型都不同。也就是说，字母后面应该跟着数字，而数字后面应该跟着字母。

请你返回 重新格式化后 的字符串；如果无法按要求重新格式化，则返回一个 空字符串 。

测试用例：

示例 1：

输入：s = "a0b1c2"
输出："0a1b2c"
解释："0a1b2c" 中任意两个相邻字符的类型都不同。 "a0b1c2", "0a1b2c", "0c2a1b" 也是满足题目要求的答案。

示例 2：

输入：s = "leetcode"
输出：""
解释："leetcode" 中只有字母，所以无法满足重新格式化的条件。

示例 3：

输入：s = "1229857369"
输出：""
解释："1229857369" 中只有数字，所以无法满足重新格式化的条件。

示例 4：

输入：s = "covid2019"
输出："c2o0v1i9d"

示例 5：

输入：s = "ab123"
输出："1a2b3"

限制及提示：

• 1 <= s.length <= 500
• s 仅由小写英文字母和/或数字组成。

---

解题分析及思路：

本题可以采用双指针的方法。

在这之前显排除不符合条件的情况，即数字和字母个数差大于1的情况，这样是凑不齐数字和字母相邻的情况。

digitNum := 0
for _, c := range s {
    if unicode.IsDigit(c) {
        digitNum++
    }
}
alphaNum := len(s) - digitNum
abs := func(x int) int {
    if x < 0 {
        return -x
    }
    return x
}
if abs(digitNum-alphaNum) > 1 {
    return ""
}

采用双指针，一个指针寻找下一个需要操作的字母，一个指针寻找下一个需要操作的数字。

使用一个标记来表明当前是寻找字母还是数字，如果字母数比数字数多的时候，该flag为true，否则则为false

• flag为true时，寻找下一个字母，并将其添加到结果中，将flag反转
• flag为false时，寻找下一个数字，并将其添加到结果中，将flag反转

需要注意，下标不可越界，所以都需要判断i < len(s)或j < len(s)

flag := digitNum < alphaNum
var ans []rune
for i, j := 0, 0; i < len(s) || j < len(s); {
    flag = !flag
    if flag {
        for i < len(s) && !unicode.IsDigit(rune(s[i])) {
            i++
        }
        if i == len(s) {
            continue
        }
        ans = append(ans, rune(s[i]))
        i++
    } else {
        for j < len(s) && unicode.IsDigit(rune(s[j])) {
            j++
        }
        if j == len(s) {
            continue
        }
        ans = append(ans, rune(s[j]))
        j++
    }
}
return string(ans)

复杂度：

• 时间复杂度：O(n)
• 空间复杂度：O(n)

执行结果：

• 执行用时：0 ms, 在所有 Go 提交中击败了100.00%的用户
• 内存消耗：3.3 MB, 在所有 Go 提交中击败了31.43%的用户