简单

问题描述

给你一个混合了数字和字母的字符串 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$，则无法满足重新格式化的条件，否则交替从两个分类中依次取出值合并到返回结果汇总，首次取数的分类应该是两个分类中数量较大的分类，若两个分类数量相同，则任意选取即可。

/**
 * @param {string} s
 * @return {string}
 */
var reformat = function (s) {
  const arr = s.split('')
  const nums = arr.filter((i) => !isNaN(+i))
  const chars = arr.filter((i) => isNaN(+i))
  const merge = (arr1, arr2) => {
    let idx = 0
    for (let i = 0; i < arr1.length; i++) {
      arr[idx] = arr1[i]
      idx += 2
    }
    idx = 1
    for (let i = 0; i < arr2.length; i++) {
      arr[idx] = arr2[i]
      idx += 2
    }
  }
  if (Math.abs(nums.length - chars.length) < 2) {
    if (nums.length > chars.length) {
      merge(nums, chars)
    } else {
      merge(chars, nums)
    }
    return arr.join('')
  }
  return ''
}

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

双指针

与分组合并解法类似，省去了分类结果的存储空间。

/**
 * @param {string} s
 * @return {string}
 */
var reformat = function (s) {
  let digitCnt = 0
  let charCnt = 0
  for (let i = 0; i < s.length; i++) {
    if (!isNaN(+s[i])) digitCnt++
    else charCnt++
  }
  if (Math.abs(digitCnt - charCnt) > 1) return ''
  let ans = ''
  let digit = 0
  let char = 0
  let charTurn = charCnt > digitCnt
  while (ans.length !== s.length) {
    if (charTurn) {
      while (!isNaN(+s[char])) char++
      ans += s[char++]
    } else {
      while (isNaN(+s[digit])) digit++
      ans += s[digit++]
    }
    charTurn = !charTurn
  }
  return ans
}

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