眾所期待的leetcode紀錄終於出了第一篇
主要是簡單紀錄一下解題的想法
今天要看的題目是22. Generate Parentheses，直接看題目：
Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
For example, given n = 3, a solution set is:
[ "((()))", "(()())", "(())()", "()(())", "()()()" ]
簡單說就是把每個合法的組合都列出來...，直接看怎麼解吧
Sol：
基本上我一開始看到這題...，直覺地想到stack，因為之前上資料結構的時候有寫過一題跟這個有點相關的題目
好像是要判斷這個Parentheses合不合法吧，大概是這樣：
bool isValid(const string& str)
{
int n = 0;
for (char c : str)
{
if (c == '(')
++n;
else
--n;
if (n < 0)
return false;
}
return (n == 0);
}
嗯...，差不多是這樣，簡單說就是看到"("就加一，看到")"就減一，然後如果堆疊是負的，那就是不合法的組合了
那跟這題有沒有關係呢，先說結論，算一半吧
因為你可以把所有的排列可能都找出來，然後通通判斷一次...
這也是一種方法啦，至於怎麼把所有的排列都找出來呢
假設有n個符號(不管是"("還是")")要被加入，可以用遞迴的方式來做：
void generateStr(string cur, int n, vector<string>& vsResult)
{
if (n == 0)
{
if (isValid(cur))
{
vsResult.push_back(cur);
}
}
else
{
generateStr(cur+"(", n - 1, vsResult);
generateStr(cur+")", n - 1, vsResult);
}
}
這樣只要generateStr("", n, vsResult)，就可以得到答案了
....
不覺得很奇怪嗎，都要傳n進去用遞迴了，換個思路看看
假設我知道有n組()要排列，而每一組的"("必須要比")"還要先出現，那我們就可以假設open為還沒放入的"("的數量，close為還沒放入的")"數量：
void generateStr(string combination, int open, int close)
所以想當然，open一開始就是n，close為0
當每排入一個open，就少一個open要排入，但多一個close排入；當排入一個close，就少一個close可以排入，open的數量不變
最後當open和close都為0的時候，就表示排完了：
void generateStr(string combination, int open, int close)
{
if (open == 0 && close == 0)
{
m_vsRet.push_back(combination);
return;
}
if (open > 0)
{
generateStr(combination + "(", open - 1, close + 1);
}
if (close > 0)
{
generateStr(combination + ")", open, close - 1);
}
}
這樣就不用檢查合不合法了，因為排的規則本身就是合法的
以n=3為例的話，就會排出["((()))", "(()())", "(())()", "()(())", "()()()"]
(總之就是能先排"("就會先排)
好吧，我承認我一開始是用第一種方法...，後來那個是別人的作法XD
不過就當作學習吧~ 這題就記錄到這了~
留言列表
