Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/1087.html
1087. Brace Expansion
Level
Medium
Description
A string S
represents a list of words.
Each letter in the word has 1 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, "{a,b,c}d{e,f}"
represents the list ["ade", "adf", "bde", "bdf", "cde", "cdf"]
.
Return all words that can be formed in this manner, in lexicographical order.
Example 1:
Input: “{a,b}c{d,e}f”
Output: [“acdf”,”acef”,”bcdf”,”bcef”]
Example 2:
Input: “abcd”
Output: [“abcd”]
Note:
1 <= S.length <= 50
- There are no nested curly brackets.
- All characters inside a pair of consecutive opening and ending curly brackets are different.
Solution
Use the idea of breadth first search. First split S
into each letter that is represented as one option or several options. Then for each letter from left to right, append each letter in the current option to previous strings to form words letter by letter. Finally, sort the complete words and return.
-
class Solution { public String[] expand(String S) { S = S.replaceAll("\\{", " \\{"); S = S.replaceAll("}", "} "); S = S.trim(); String[] array = S.split(" "); Queue<String> queue = new LinkedList<String>(); int length = array.length; for (int i = 0; i < length; i++) { String curStr = array[i]; if (curStr.indexOf('{') >= 0) curStr = curStr.substring(1, curStr.length() - 1); String[] curArray = curStr.split(","); int curSize = queue.size(); if (curSize == 0) { for (String str : curArray) queue.offer(str); } else { for (int j = 0; j < curSize; j++) { String prev = queue.poll(); for (String str : curArray) queue.offer(prev + str); } } } int size = queue.size(); String[] words = new String[size]; for (int i = 0; i < size; i++) words[i] = queue.poll(); Arrays.sort(words); return words; } }
-
// OJ: https://leetcode.com/problems/brace-expansion/ // Time: O(NK) where K is the total number of possible branches // Space: O(N) class Solution { public: vector<string> expand(string s) { vector<vector<char>> v; for (int i = 0, N = s.size(); i < N; ++i) { if (s[i] == '{') { ++i; v.emplace_back(); while (s[i] != '}') { v.back().push_back(s[i++]); if (s[i] == ',') ++i; } sort(begin(v.back()), end(v.back())); } else v.push_back({ s[i] }); } vector<string> ans; string tmp; function<void(int)> dfs = [&](int i) { if (i == v.size()) { ans.push_back(tmp); return; } for (int j = 0; j < v[i].size(); ++j) { tmp += v[i][j]; dfs(i + 1); tmp.pop_back(); } }; dfs(0); return ans; } };
-
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