LeetCode 1096. 花括号展开 II

Categories:

题目描述
思路分析
1. 解法一：递归解析表达式（推荐）
相似题目

题目描述

✅ 1096. 花括号展开 II

思路分析

解法一：递归解析表达式（推荐）

核心思路：

按语法递归：expr = term {, term}，term = factor {factor}。

factor 可能是单词或 {expr}。

使用集合做去重，最后按字典序输出。

复杂度分析：

时间复杂度：O(k log k)，其中 k 为展开后字符串数量。

空间复杂度：O(k)。

import java.util.*;

class Solution {
    public List<String> braceExpansionII(String expression) {
        int[] idx = new int[1];
        Set<String> res = parseExpr(expression, idx);
        List<String> list = new ArrayList<>(res);
        Collections.sort(list);
        return list;
    }

    private Set<String> parseExpr(String s, int[] idx) {
        Set<String> res = parseTerm(s, idx);
        while (idx[0] < s.length() && s.charAt(idx[0]) == ',') {
            idx[0]++;
            res.addAll(parseTerm(s, idx));
        }
        return res;
    }

    private Set<String> parseTerm(String s, int[] idx) {
        Set<String> res = new HashSet<>();
        res.add("");
        while (idx[0] < s.length() && s.charAt(idx[0]) != '}' && s.charAt(idx[0]) != ',') {
            Set<String> next = parseFactor(s, idx);
            Set<String> merged = new HashSet<>();
            for (String a : res) {
                for (String b : next) {
                    merged.add(a + b);
                }
            }
            res = merged;
        }
        return res;
    }

    private Set<String> parseFactor(String s, int[] idx) {
        Set<String> res = new HashSet<>();
        if (s.charAt(idx[0]) == '{') {
            idx[0]++;
            res = parseExpr(s, idx);
            idx[0]++;
            return res;
        }

        StringBuilder sb = new StringBuilder();
        while (idx[0] < s.length()) {
            char c = s.charAt(idx[0]);
            if (c == '{' || c == '}' || c == ',') {
                break;
            }
            sb.append(c);
            idx[0]++;
        }
        res.add(sb.toString());
        return res;
    }
}

import "sort"

func braceExpansionII(expression string) []string {
    idx := 0
    res := parseExpr(expression, &idx)
    list := make([]string, 0, len(res))
    for k := range res {
        list = append(list, k)
    }
    sort.Strings(list)
    return list
}

func parseExpr(s string, idx *int) map[string]struct{} {
    res := parseTerm(s, idx)
    for *idx < len(s) && s[*idx] == ',' {
        *idx = *idx + 1
        term := parseTerm(s, idx)
        for k := range term {
            res[k] = struct{}{}
        }
    }
    return res
}

func parseTerm(s string, idx *int) map[string]struct{} {
    res := map[string]struct{}{"": {}}
    for *idx < len(s) && s[*idx] != '}' && s[*idx] != ',' {
        next := parseFactor(s, idx)
        merged := make(map[string]struct{})
        for a := range res {
            for b := range next {
                merged[a+b] = struct{}{}
            }
        }
        res = merged
    }
    return res
}

func parseFactor(s string, idx *int) map[string]struct{} {
    res := make(map[string]struct{})
    if s[*idx] == '{' {
        *idx = *idx + 1
        res = parseExpr(s, idx)
        *idx = *idx + 1
        return res
    }

    start := *idx
    for *idx < len(s) {
        c := s[*idx]
        if c == '{' || c == '}' || c == ',' {
            break
        }
        *idx = *idx + 1
    }
    res[s[start:*idx]] = struct{}{}
    return res
}

相似题目

题目	难度	考察点
1087. 花括号展开	中等	递归
22. 括号生成	中等	回溯
241. 为运算表达式设计优先级	中等	递归
385. 迷你语法分析器	中等	解析
1096. 花括号展开 II	困难	递归解析

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2022/14174266