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.
A:
就是个Permuation 的问题
一层层加上去就是了
class Solution { public: vector<string> expand(string S) { vector<vector<char>> V; int start = 0; int n = S.length(); while(start<n){ int end = start; if(S[end]!= '{'){ V.push_back(vector<char>{S[end]}); start++; }else{ while(end<n && S[end]!='}'){ end++; } V.push_back(vector<char>()); for(int i =start+1;i<end;i+=2){ V.back().push_back(S[i]); } start = end+1; } } // vector<string> res; if(V.size()==0) return res; res.push_back(""); for(auto line : V){ vector<string> newRes; for(auto ch : line){ for(auto& t : res){ newRes.push_back( t+ string(1,ch) ); } } res = newRes; } sort(res.begin(), res.end()); // sort in Lexicographical order return res; } };
No comments:
Post a Comment