The Brace Expansion Algorithms using Breadth First Search or Dep

  • 时间：2020-09-25 11:32:47
  • 分类：网络文摘
  • 阅读：144 次

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.

Assume the string is well-formed e.g. the curly braces must come in pairs and there is no nested curly braces. Also, apart from lowercase letters, curly braces, commas, there are not other characters such as whitespaces.

The first step is to pre-process the input and group into a two dimensional list, which can be represented via vector of vector of characters. Depending on the search algorithm, we can have Depth First Search (DFS) or Breadth First Search (BFS).

String Brace Expansion via Breadth First Search Algorithm

For Breadth First Search BFS to work, we first put the empty string to the queue (the search should start with empty string), then when we get a node from the queue, we push its children to the queue. At last, when the string is constructed (we check the length), we add it to the result vector.

Also, we need to sort the result in order to return the list in in lexicographical order.

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

class Solution {
public:
    vector<string> expand(string S) {
        vector<vector<char>> data;
        int n = S.size(), i = 0;        
        while (i < n) {
            if (isalpha(S[i])) { // single character
                data.push_back({S[i]});
                i ++;
            } else {  // a list of options
                i ++;
                int j = i;
                vector<char> cur = {};
                while (S[j] != '}') {
                    if (S[j] != ',') { // skip delimiter
                        cur.push_back(S[j]); // split on the fly
                    }
                    j ++;
                }                
                data.push_back(cur); // push current option list
                i = j + 1;
            }            
        }
        queue<string> Q;
        Q.push("");
        vector<string> r;
        while (!Q.empty()) {
            auto p = Q.front();
            Q.pop();
            if (p.size() == data.size()) { // we have a fully constructed answer
                r.push_back(p); 
            } else {
                int x = p.size();
                for (int i = 0; i < data[x].size(); ++ i) {
                    Q.push(p + data[x][i]); // add children for next level
                }
            }
        }
        std::sort(begin(r), end(r));
        return r;
    }
};
class Solution {
public:
    vector<string> expand(string S) {
        vector<vector<char>> data;
        int n = S.size(), i = 0;        
        while (i < n) {
            if (isalpha(S[i])) { // single character
                data.push_back({S[i]});
                i ++;
            } else {  // a list of options
                i ++;
                int j = i;
                vector<char> cur = {};
                while (S[j] != '}') {
                    if (S[j] != ',') { // skip delimiter
                        cur.push_back(S[j]); // split on the fly
                    }
                    j ++;
                }                
                data.push_back(cur); // push current option list
                i = j + 1;
            }            
        }
        queue<string> Q;
        Q.push("");
        vector<string> r;
        while (!Q.empty()) {
            auto p = Q.front();
            Q.pop();
            if (p.size() == data.size()) { // we have a fully constructed answer
                r.push_back(p); 
            } else {
                int x = p.size();
                for (int i = 0; i < data[x].size(); ++ i) {
                    Q.push(p + data[x][i]); // add children for next level
                }
            }
        }
        std::sort(begin(r), end(r));
        return r;
    }
};

The BFS expands the search levels by levels (characters by characters), which means it will now quickly find a solution, Rather, it will construct the solutions one by one until the last possible letter.

String Brace Expansion via Breadth Depth Search Algorithm

The Depth Search Algorithm DFS works slightly differently and is usually implemented via recursion. Instead of level-by-level search, it will quickly go as deep as possible, that means it will usually find a solution quicker.

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

class Solution {
public:
    vector<string> expand(string S) {
        vector<vector<char>> data;
        int n = S.size(), i = 0;        
        while (i < n) {
            if (isalpha(S[i])) { // store a single character
                data.push_back({S[i]});
                i ++;
            } else { // we have come to { .. } 
                i ++;
                int j = i;
                vector<char> cur = {};
                while (S[j] != '}') { // when the curly brace is not finished
                    if (S[j] != ',') { // skip the delimiter
                        cur.push_back(S[j]); // push to the current list
                    }
                    j ++;
                }                
                data.push_back(cur); // store the current list
                i = j + 1; // navigate to the next group
            }            
        }
        vector<string> r;
        dfs(data, 0, r, "");
        std::sort(begin(r), end(r));
        return r;
    }
 
private:
    void dfs(const vector<vector<char>> &data, int idx, vector<string> &r, string p) {
        if (p.size() == data.size()) { // the brace expansion is finished.
            r.push_back(p);
            return;
        }
        for (int i = 0; i < data[idx].size(); ++ i) { // iterate over current list
            dfs(data, idx + 1, r, p + data[idx][i]); // pick next group
        }
    }
};
class Solution {
public:
    vector<string> expand(string S) {
        vector<vector<char>> data;
        int n = S.size(), i = 0;        
        while (i < n) {
            if (isalpha(S[i])) { // store a single character
                data.push_back({S[i]});
                i ++;
            } else { // we have come to { .. } 
                i ++;
                int j = i;
                vector<char> cur = {};
                while (S[j] != '}') { // when the curly brace is not finished
                    if (S[j] != ',') { // skip the delimiter
                        cur.push_back(S[j]); // push to the current list
                    }
                    j ++;
                }                
                data.push_back(cur); // store the current list
                i = j + 1; // navigate to the next group
            }            
        }
        vector<string> r;
        dfs(data, 0, r, "");
        std::sort(begin(r), end(r));
        return r;
    }

private:
    void dfs(const vector<vector<char>> &data, int idx, vector<string> &r, string p) {
        if (p.size() == data.size()) { // the brace expansion is finished.
            r.push_back(p);
            return;
        }
        for (int i = 0; i < data[idx].size(); ++ i) { // iterate over current list
            dfs(data, idx + 1, r, p + data[idx][i]); // pick next group
        }
    }
};

Both solutions run at the same time complexity as the combination is the same (length of result set).

–EOF (The Ultimate Computing & Technology Blog) —

推荐阅读：
北山移文原文及翻译　 五柳先生传原文及翻译　 桃花源记原文及翻译　 进水排水的牛吃草问题　 汽车运化肥的牛吃草问题　 下面的哪个分数大　 扩大鱼池问题　 巧分食盐水问题　 均分田地问题　 切西瓜的数学问题　
评论列表
添加评论