# Halo

A magic place for coding

0%

## Problem

You are given a string s representing a list of words. Each letter in the word has one or more options.

• If there is one option, the letter is represented as is.
• If there is more than one option, then curly braces delimit the options. For example, "{a,b,c}" represents options ["a", "b", "c"].

For example, if s = "a{b,c}", the first character is always 'a', but the second character can be 'b' or 'c'. The original list is ["ab", "ac"].

Return all words that can be formed in this manner, sorted in lexicographical order.

Example 1:

Example 2:

Constraints:

• 1 <= s.length <= 50
• s consists of curly brackets '{}', commas ',', and lowercase English letters.
• s is guaranteed to be a valid input.
• There are no nested curly brackets.
• All characters inside a pair of consecutive opening and ending curly brackets are different.

## Analysis

题目给出一个字符串s，如果是以{}包括的字符，说明是可选的，否则就是必须要使用的，要求返回所有的情况。这个BFS了，每次都需要把队列中所有的元素拿出来，添加一个候选字符，只不过这个候选字符有两种情况：

1. 只有一个字符，必选；
2. {}包括的字符，有多个；

所以我们处理的方法就是如果处理到{，就把括号内的所有字符加入到候选字符；如果处理到的是单个字符，就把单个字符加入到候选字符。然后把队列遍历一遍，把里面的元素都拿出来，加上候选字符重新放到队列中，最后把队列中的字符串都放到vector中即可。

无。

## Summary

这道题目和decode string有点类似但是完全不同的解法，decode string因为存在嵌套关系，所以用到了stack，而这里并没有嵌套的关系，而是组合关系，所以用BFS。这道题目的分享到这里，感谢你的支持！

Welcome to my other publishing channels