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. 1 <= S.length <= 50
  2. There are no nested curly brackets.
  3. 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

All Problems

All Solutions