Leetcode 1087. Brace Expansion

Problem Explanation

Given a string that represents a list of words, return all words that can be formed in it, in lexicographical order. Each letter in the word has 1 or more options. If there is one option, the letter should be 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"] and "{a,b,c}d{e,f}" represents the list ["ade", "adf", "bde", "bdf", "cde", "cdf"].

Walk Through Example

Consider the input "{"a,b,c}d{e,f}". Here, there are 3 options for the first character i.e. [a, b, c], only one option dfor the second character, 2 options for the third character[e, f]. So the possible combinations or words would be ade, adf, bde, bdf, cde, cdf`.

To solve this problem, we could use the Depth First Search (DFS) method, where we initially gather the options in each given group and subsequently traverse through the possibilities of each option in the string.

Python Solution

1
2Python
3class Solution:
4    def expand(self, S: str) -> List[str]:
5        groups = S.replace("{"," ").replace("}"," ").split()
6        options = [sorted(g.split(',')) for g in groups]
7        ans = [""]
8
9        for option in options:
10            ans = [a + c for a in ans for c in option]
11
12        return ans

Java Solution

1
2Java
3class Solution {
4    public String[] expand(String S) {
5        String[] parts = S.split(",");
6        Arrays.sort(parts);
7        return dfs(parts, 0);
8    }
9
10    private String[] dfs(String[] parts, int index) {
11        if (index == parts.length) {
12            return new String[]{""};
13        }
14
15        String[] rest = dfs(parts, index + 1);
16        List<String> result = new ArrayList<>();
17
18        for (String p : parts[index].split(",")) {
19            for (String r : rest) {
20                result.add(p + r);
21            }
22        }
23
24        return result.toArray(new String[0]);
25    }
26}

JavaScript Solution

1
2Javascript
3var expand = function(S) {
4    S = S.split("{");
5    S = S.map(x=>x.split("}"));
6    var res = [""];
7    for(var i =0;i<S.length;i++){
8        var temp = [];
9        var list = S[i][0].split(",");
10        let j = 1;
11        while(S[i][j]){
12            list = list.map(x=>x+S[i][j]);
13            j++;
14        }
15        list.sort();
16        while(res.length){
17            var cur = res.pop();
18            for(var k =0;k<list.length;k++){
19                temp.push(cur+list[k]);
20            }
21        }
22        res = temp;
23    }
24    return res;
25};

C++ Solution

1
2C++
3class Solution {
4public:
5    vector<string> expand(string S) {
6        vector<string> groups = split(S, ',');
7        for (string &group : groups)
8            sort(group.begin(), group.end());
9
10        return dfs(groups, 0);
11    }
12
13private:
14    vector<string> dfs(vector<string> &groups, int i) {
15        if (i == groups.size())
16            return {""};
17        
18        vector<string> results;
19        vector<string> tails = dfs(groups, i+1);
20        for (char head : groups[i]) {
21            for (string tail : tails) {
22                results.push_back(head + tail);
23            }
24        }
25        return results;
26    }
27
28    vector<string> split(const string &s, char c) {
29        vector<string> tokens;
30        stringstream ss(s);
31        string token;
32        while (getline(ss, token, c))
33            tokens.push_back(token);
34        return tokens;
35    }
36};

C# Solution

1
2Csharp
3public class Solution {
4    public IList<string> Expand(string S) {
5        var parts = S.Split(',');
6        Array.Sort(parts);
7        return Expand(parts, 0).ToList();
8    }
9
10    private string[] Expand(string[] parts, int index) {
11        if (index == parts.Length) return new string[] { "" };
12        
13        var rest = Expand(parts, index + 1);
14        var result = new List<string>();
15        
16        foreach (var p in parts[index].Split(',')) {
17            foreach (var r in rest) {
18                result.Add(p + r);
19            }
20        }
21        return result.ToArray();
22    }
23}

In the above examples, we have taken different approaches for different languages. In Python, we have replaced the curly braces with spaces and then split the strings based on spaces so that we get all the groups. Within each group, we have created a list of available options by splitting with commas. Then, we traverse from left to right and keep appending the available options on the right to the existing list in the left. This way we get all possible combinations in a lexicographical sorted way. Our Java and C# solutions are quite similar, wherein we have used recursive calls, but we have split the string based on commas right at the beginning. After that, we have recursively called the same function on the rest of the strings left and in each call, we have created a result list by appending the available option with the rest of the string received from the recursive calls. Finally, we have returned the result array of combinations. JavaScript follows a different approach, where we first split the string based on curly braces and then we iterate through each group and append the subsequent group to it and sort and push to the result array. The C++ solution is quite similar to Java and C# where we have used recursive calls, but we have used a different function to split the string into groups.

These varied approaches show how the problem can be solved differently in different languages, while still achieving the same result which is - returning all possible combinations of words in lexicographical order. These solutions are not unique and can be optimized or changed as per one's coding style or preference. The important thing is understanding the problem and the logic to solve it, as the syntax can be adapted as per the language used.