The Brace Expansion Algorithms using Breadth First Search or Dep

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

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.

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.

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

评论列表

添加评论: 姓名：　验证码：