難度: Medium
類型: String, Dynamic Programming, Backtracking
CPP程式下載: 22.cpp
前情題要:
列出所有N 個括弧的可能組合
思考方式:
1. 利用 Set 的唯一性, 我們就不避自己實作比對的程式。把所有可能的組合往裡面丟就好。
2. 給一組括弧當開始。
兩組括弧就是在字串最左邊加上"()", 找到第一個"("之後加上"()", 最後在字串最右邊加上"()‧‧。
三組括弧就是在字串最左邊加上"()", 找到第一個"("之後加上"()", 找到第二個"("之後加上"()", 最後在字串最右邊加上"()‧‧。
後面以此類推
3. 最後記得把Set的每個 string, 都存到 vector <string> 中。
複雜度思考:
Time Complexity: O( N+(N-1)+....+2 )
Space Complexity: O( x )
結果:
Runtime: 3 ms, Beats: 71.36%
Memory: 11.29 MB, Beats: 96.48%
