1417. 重新格式化字符串

🟢   🔖  字符串  🔗 力扣 LeetCode

题目

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.

题目大意

给你一个混合了数字和字母的字符串 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. 分类字符：

   • 遍历字符串 s，将其中的数字存入数组 digit，字母存入数组 alphabet。
   • 使用正则表达式 /^[0-9]$/ 判断字符是否为数字。

2. 检查是否可重排：

   • 如果数字与字母的数量差绝对值大于 1，则无法交替排列，返回空字符串 ""。

3. 交替排列：

   • 根据 digit 和 alphabet 的长度决定哪一组先开始（长的那组先）。
   • 遍历较长数组，同时从两组中交替拼接字符。

4. 拼接结果：

   • 将交替拼接的结果存储到字符串 res 中。
   • 如果某组长度多出一个字符，会自动拼接到末尾。

5. 返回结果：

   • 返回最终的 res。

复杂度分析

• 时间复杂度：O(n)，其中 n 是字符串 s 的长度，遍历字符串一次，拼接结果也只需线性时间。
• 空间复杂度：O(n)，需要存储两个数组 digit 和 alphabet。

代码

/**
 * @param {string} s
 * @return {string}
 */
var reformat = function (s) {
	let digit = [];
	let alphabet = [];

	// 分类字符
	for (let char of s) {
		if (/^[0-9]$/.test(char)) {
			digit.push(char);
		} else {
			alphabet.push(char);
		}
	}

	// 检查是否可重排
	if (Math.abs(digit.length - alphabet.length) > 1) return '';

	// 交替排列
	let res = '';
	let longer = digit.length >= alphabet.length ? digit : alphabet;
	let shorter = digit.length < alphabet.length ? digit : alphabet;

	for (let i = 0; i < longer.length; i++) {
		res += longer[i];
		if (shorter[i]) {
			res += shorter[i];
		}
	}

	return res;
};