LeetCode 1087. 花括号展开

Categories:

题目描述
思路分析
1. 解法一：逐段展开（推荐）
相似题目

题目描述

✅ 1087. 花括号展开

思路分析

解法一：逐段展开（推荐）

核心思路：

从左到右解析字符串，遇到普通字符直接拼接。

遇到花括号时解析备选字符列表，与当前结果做笛卡尔积。

最终结果按字典序排序。

复杂度分析：

时间复杂度：O(k * r)，其中 r 为结果数量，k 为平均字符串长度。

空间复杂度：O(r * k)，用于存储结果。

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

class Solution {
    public String[] expand(String s) {
        List<String> res = new ArrayList<>();
        res.add("");

        int i = 0;
        while (i < s.length()) {
            List<String> options = new ArrayList<>();

            if (s.charAt(i) == '{') {
                i++;
                while (i < s.length() && s.charAt(i) != '}') {
                    if (s.charAt(i) != ',') {
                        options.add(String.valueOf(s.charAt(i)));
                    }
                    i++;
                }
                i++;
            } else {
                options.add(String.valueOf(s.charAt(i)));
                i++;
            }

            List<String> next = new ArrayList<>();
            for (String prefix : res) {
                for (String opt : options) {
                    next.add(prefix + opt);
                }
            }
            res = next;
        }

        Collections.sort(res);
        return res.toArray(new String[0]);
    }
}

import "sort"

func expand(s string) []string {
	res := []string{""}

	i := 0
	for i < len(s) {
		options := make([]string, 0)

		if s[i] == '{' {
			i++
			for i < len(s) && s[i] != '}' {
				if s[i] != ',' {
					options = append(options, string(s[i]))
				}
				i++
			}
			i++
		} else {
			options = append(options, string(s[i]))
			i++
		}

		next := make([]string, 0)
		for _, prefix := range res {
			for _, opt := range options {
				next = append(next, prefix+opt)
			}
		}
		res = next
	}

	sort.Strings(res)
	return res
}

相似题目

题目	难度	考察点
1087. 花括号展开	中等	解析、组合
1088. 花括号展开 II	困难	解析、递归
784. 字母大小写全排列	中等	DFS
22. 括号生成	中等	回溯
17. 电话号码的字母组合	中等	回溯

本文作者: HGNULB

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