LeetCode 1417. 重新格式化字符串

Categories:

题目描述
思路分析
1. 解法一：双队列交替拼接（推荐）
相似题目

题目描述

✅ 1417. 重新格式化字符串

思路分析

解法一：双队列交替拼接（推荐）

核心思路：

分离字母与数字，若数量差超过 1 则无法重排。

以数量较多的一类先放，再交替拼接。

复杂度分析：

时间复杂度：O(n)。

空间复杂度：O(n)。

class Solution {
    public String reformat(String s) {
        StringBuilder digits = new StringBuilder();
        StringBuilder letters = new StringBuilder();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (Character.isDigit(c)) {
                digits.append(c);
            } else {
                letters.append(c);
            }
        }

        if (Math.abs(digits.length() - letters.length()) > 1) {
            return "";
        }

        StringBuilder res = new StringBuilder();
        boolean digitFirst = digits.length() > letters.length();
        int i = 0;
        while (i < digits.length() || i < letters.length()) {
            if (digitFirst && i < digits.length()) {
                res.append(digits.charAt(i));
            }
            if (i < letters.length()) {
                res.append(letters.charAt(i));
            }
            if (!digitFirst && i < digits.length()) {
                res.append(digits.charAt(i));
            }
            i++;
        }
        return res.toString();
    }
}

func reformat(s string) string {
    digits := make([]byte, 0)
    letters := make([]byte, 0)
    for i := 0; i < len(s); i++ {
        c := s[i]
        if c >= '0' && c <= '9' {
            digits = append(digits, c)
        } else {
            letters = append(letters, c)
        }
    }

    if abs(len(digits)-len(letters)) > 1 {
        return ""
    }

    res := make([]byte, 0, len(s))
    digitFirst := len(digits) > len(letters)
    i := 0
    for i < len(digits) || i < len(letters) {
        if digitFirst && i < len(digits) {
            res = append(res, digits[i])
        }
        if i < len(letters) {
            res = append(res, letters[i])
        }
        if !digitFirst && i < len(digits) {
            res = append(res, digits[i])
        }
        i++
    }
    return string(res)
}

func abs(x int) int {
    if x < 0 {
        return -x
    }
    return x
}

相似题目

题目	难度	考察点
824. 山羊拉丁文	简单	字符串处理
709. 转换成小写字母	简单	字符串
125. 验证回文串	简单	字符串
344. 反转字符串	简单	字符串
1108. IP 地址无效化	简单	字符串

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2024/84636525