The Brace Expansion Algorithms using Breadth First Search or Dep

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

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

推荐阅读：
山东体育频道直播-山东体育在线直播观看「高清」　 GTV电子体育直播-电子体育在线直播观看「高清」　 中天新闻台电视直播台湾中天新闻台简介在线直播　 香港卫视新闻综合电视台直播香港卫视在线直播　 凤凰卫视香港台直播「高清」　 香港卫视直播「高清」　 阳光卫视在线直播「高清」　 亚洲联合卫视直播「高清」　 香港TVB8直播「高清」　 卫视体育台直播_星空卫视体育台直播观看「高清」　
评论列表
添加评论