leetcode
leetcode 1301 ~ 1350
重新格式化字符串

重新格式化字符串

难度:

标签:

题目描述

代码结果

运行时间: 28 ms, 内存: 16.8 MB


/*
 * 思路:
 * 1. 使用Stream将字符串中的字母和数字分别分离出来。
 * 2. 如果字母和数字的数量差超过1,返回空字符串。
 * 3. 将字母和数字交替合并到新的字符串中。
 */
import java.util.List;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class ReformatStringStream {
    public String reformat(String s) {
        List<Character> letters = s.chars()
                                    .mapToObj(c -> (char) c)
                                    .filter(Character::isLetter)
                                    .collect(Collectors.toList());
        List<Character> digits = s.chars()
                                   .mapToObj(c -> (char) c)
                                   .filter(Character::isDigit)
                                   .collect(Collectors.toList());
        if (Math.abs(letters.size() - digits.size()) > 1) {
            return "";
        }
        StringBuilder result = new StringBuilder();
        boolean letterFirst = letters.size() >= digits.size();
        while (!letters.isEmpty() || !digits.isEmpty()) {
            if (letterFirst && !letters.isEmpty()) {
                result.append(letters.remove(0));
            } else if (!letterFirst && !digits.isEmpty()) {
                result.append(digits.remove(0));
            }
            letterFirst = !letterFirst;
        }
        return result.toString();
    }
}

解释

方法:

题目要求将字符串重新格式化,使得任意两个相邻字符的类型都不同(字母和数字交替出现)。首先检查字符串是否只含有一种字符(全部是字母或者全部是数字),如果是,则直接返回空字符串。接着,遍历字符串,将数字和字母分别存储到两个列表中。如果两个列表的长度差大于1,也返回空字符串,因为无法按要求格式化。最后,根据两个列表的长度关系,交替从两个列表中取出元素拼接到结果字符串中,确保较长的列表元素先取。如果有剩余的元素(只会剩下一个),则追加到结果字符串的末尾。

时间复杂度:

O(n)

空间复杂度:

O(n)

代码细节讲解

🦆
为什么在只有字母或只有数字的情况下,直接返回空字符串?是否有其他可能的输出格式?
题目的要求是必须使得新格式化的字符串中任意两个相邻的字符一个是字母,另一个是数字。如果输入字符串只包含字母或者只包含数字,就不可能创建一个符合条件的字符串,因为无法提供必要的交替字符类型。因此,在这种情况下,返回空字符串是表示无法按题目要求格式化的一种明确方式。没有其他可能的输出格式,因为任何包含字符的输出都将违反题目的格式要求。
🦆
算法中为何选择先检查字母和数字的数量差异大于1就返回空字符串,这里的逻辑依据是什么?
如果字母和数字的数量差异大于1,意味着无法平衡地交替它们以满足题目的要求。例如,如果有3个字母和1个数字,最多只能形成'字母-数字-字母'的结构,此时还剩一个字母无法与数字交替。因此,当数量差异大于1时,无论如何也无法格式化成符合要求的字符串,所以返回空字符串是避免无效尝试的合理选择。
🦆
当字母和数字数量相等时,是否有特定的顺序要求来开始拼接字符串,例如先字母还是先数字?
当字母和数字数量相等时,可以从任一类型开始拼接字符串。可以是'字母-数字'也可以是'数字-字母',因为无论从哪种类型开始,都可以确保每个字母和数字之间都紧跟着另一种类型的字符。因此,没有严格的顺序要求,可以根据具体情况或者偏好来选择开始的字符类型。
🦆
算法中提到如果列表中还有剩余的字母或数字会追加到结果字符串的末尾,这种情况是如何保证仍然满足任意两个相邻字符类型不同的要求?
在任意一个类型的列表中剩余元素时,这种情况只能发生当一个列表比另一个列表多一个元素。在这种情况下,剩余的元素总是与最后一个加入结果的元素类型不同。例如,如果字母列表多出一个元素,那么在所有数字已经被交替添加后,最后添加的肯定是数字,因此剩余的字母添加到末尾时,依旧保持了交替的规则。这确保了结果字符串中任意两个相邻字符的类型仍然是不同的。

相关问题