Remove Invalid Parentheses
Remove the minimum number of invalid parentheses in order to make the input string valid. Return all possible results.
Note: The input string may contain letters other than the parentheses (
and )
.
Example 1: Input : "( ) ( ) ) ( )" Output : ["( ) ( ) ( )", "( ( ) ) ( )"]
Example 2 : Input : "(a)( ) ) ( )" Output : ["(a)( ) ( )", "(a( ) ) ( )"]
Example 3: Input: ") (" Output: [" "]
์๋ฃ๊ตฌ์กฐ : Queue, Set์ด์ฉ
์๊ณ ๋ฆฌ์ฆ input String์ 0๋ฒ์งธ index ๋ถํฐ ๋ง์ง๋ง index๊น์ง ํ๋์ฉ ์ ๊ฑฐํด์ ์ ํจ์ฑ ๊ฒ์ฌํ๋ค. 1. input String์ ํ์ ๋ฃ๋๋ค. 2. ํ์์ string์ ๋นผ๋ฉด์ ์ ํจ์ฑ ๊ฒ์ฌํ๋ค. ํ์์ ๋บ string์ธ str์ด validํ๋ค๋ฉด result๊ฐ ๋๋ค. ๊ทธ๋ฆฌ๊ณ ๋์ด์ ๋ฐ๋ณต๋ฌธ์ ์ํํ์ง ์์๋ ๋๋ค. ํ์์ n๊ฐ๋ฅผ ์ ๊ฑฐํ string์ธ str์ด invalidํ๋ค๋ฉด, ๊ทธ ๋ค์ n๊ฐ๋ฅผ ์ ๊ฑฐํ string์ ์ํํ๋ค.(BFS)
Last updated