LeetCode 1087. Brace Expansion Solution in Java & Python | Explanation + Code

Description

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 <= 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.

Solutions

Solution 1

PythonJava

class Solution: def expand(self, s: str) -> List[str]: def convert(s): if not s: return if s[0] == '{': j = s.find('}') items.append(s[1:j].split(',')) convert(s[j + 1 :]) else: j = s.find('{') if j != -1: items.append(s[:j].split(',')) convert(s[j:]) else: items.append(s.split(',')) def dfs(i, t): if i == len(items): ans.append(''.join(t)) return for c in items[i]: t.append(c) dfs(i + 1, t) t.pop() items = [] convert(s) ans = [] dfs(0, []) ans.sort() return ans(code-box)

class Solution { private List<String> ans; private List<String[]> items; public String[] expand(String s) { ans = new ArrayList<>(); items = new ArrayList<>(); convert(s); dfs(0, new ArrayList<>()); Collections.sort(ans); return ans.toArray(new String[0]); } private void convert(String s) { if ("".equals(s)) { return; } if (s.charAt(0) == '{') { int j = s.indexOf("}"); items.add(s.substring(1, j).split(",")); convert(s.substring(j + 1)); } else { int j = s.indexOf("{"); if (j != -1) { items.add(s.substring(0, j).split(",")); convert(s.substring(j)); } else { items.add(s.split(",")); } } } private void dfs(int i, List<String> t) { if (i == items.size()) { ans.add(String.join("", t)); return; } for (String c : items.get(i)) { t.add(c); dfs(i + 1, t); t.remove(t.size() - 1); } } }(code-box)