LeetCode 38. 外观数列

Categories:

题目描述
思路分析
1. 解法一：字符串分组计数（推荐）
相似题目

题目描述

✅ 38. 外观数列

思路分析

解法一：字符串分组计数（推荐）

核心思路：

从初始字符串 “1” 开始，连续生成 n-1 次下一项。

每次遍历当前字符串，按连续相同字符分组，拼接 “数量 + 字符”。

新字符串替换旧字符串，直到生成第 n 项。

复杂度分析：

时间复杂度：O(L)，其中 L 为最终字符串长度。

空间复杂度：O(L)，需要构造新字符串。

class Solution {
    public String countAndSay(int n) {
        String cur = "1";

        for (int i = 2; i <= n; i++) {
            StringBuilder sb = new StringBuilder();
            int idx = 0;

            // 分组统计连续字符
            while (idx < cur.length()) {
                int start = idx;
                char ch = cur.charAt(idx);
                while (idx < cur.length() && cur.charAt(idx) == ch) {
                    idx++;
                }

                sb.append(idx - start).append(ch);
            }

            cur = sb.toString();
        }

        return cur;
    }
}

import "strconv"

func countAndSay(n int) string {
	cur := "1"

	for i := 2; i <= n; i++ {
		builder := make([]byte, 0, len(cur)*2)
		idx := 0

		// 分组统计连续字符
		for idx < len(cur) {
			start := idx
			ch := cur[idx]
			for idx < len(cur) && cur[idx] == ch {
				idx++
			}

			count := idx - start
			builder = append(builder, []byte(strconv.Itoa(count))...)
			builder = append(builder, ch)
		}

		cur = string(builder)
	}

	return cur
}

相似题目

题目	难度	考察点
443. 压缩字符串	中等	双指针 + 计数
696. 计数二进制子串	简单	分组统计
459. 重复的子字符串	简单	字符串处理
415. 字符串相加	简单	字符串模拟
1668. 最大重复子字符串	简单	字符串匹配

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2023/92687580