The Brace Expansion Algorithms using Breadth First Search or Dep

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

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) —

推荐阅读：
站长如何创业赚钱？　 妈妈的节日母亲节作文250字　 中秋节的夜晚_关于中秋赏月的小学生作文400字　 六一儿童节的记忆作文　 中国教师节献给老师的礼物作文800字　 关于元旦节的作文600字　 家乡的上灯节作文　 欢乐的火把节_描写少数民族节日的小学生作文800字　 欢欢喜喜闹元宵_关于描写元宵佳节的小学生作文350字　 元旦节的作文300字　
评论列表
添加评论