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