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) —
loading...
Last Post: Coding Exercise: Sum of Digits in the Minimum Number
Next Post: A Microsoft Coding Interview Screening for Position Principal Software Engineer
Whats the time complexity of this problem? worst case would be something like {a,b,c}{a,b,c}{a,b,c} correct?
Good question, If there are n groups and average m elements in each group, the time complexity will be something like m^n.