LC: 1087. Brace Expansion
https://leetcode.com/problems/brace-expansion/
1087. Brace Expansion
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:
Input: s = "{a,b}c{d,e}f"
Output: ["acdf","acef","bcdf","bcef"]Example 2:
Input: s = "abcd"
Output: ["abcd"]Constraints:
1 <= s.length <= 50sconsists of curly brackets'{}', commas',', and lowercase English letters.sis 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.
The Essence:
Die Zeichen innerhalb eines “Brace-Expansions” werden mit dem “Brace-Expansions” nach rechts konkatiniert, die selbst “Brace-Expansions” enthalten kann:
Als Beispiel: expand({a, b}e{c, d}) = {a, b} + expand(e{c, d})
Man erkennt hier auch eine rekursive Struktur.
Details:
Die Rekursion kann man durch 2 Methode anwenden:
DFS: Für jede Zeichen in Klammern kann man zuerst alle mögliche Brace-Expansions nach rechts zufügen.
Der Problemlöser kann die Zeichen und Teilstrings nach links mit dem Zeichen nach rechts konkatinieren und somit alle Kombinationen der Strings erstellen.
Solutions:
Default Code:
Last updated