22. Generate Parentheses

 22. Generate Parentheses

難度: 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%

17. Letter Combinations of a Phone Number

 17. Letter Combinations of a Phone Number

難度: Medium

類型: Table, String, Backtracking

CPP程式下載: 17.cpp

前情題要:

就如傳統按鍵手機把數字轉成英文字母

思考方式:

因為最多只按四下, 最多不過 4^4=256 次, 簡單寫就好。

複雜度思考:

Time Complexity: O( 4^4 ) 

Space Complexity: O( 1 )

結果:

Runtime: 0 ms, Beats: 100%

Memory: 8.96 MB, Beats: 95.04%