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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32 | 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
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44 | 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);
}
}
}
|