괄호 '(' , ')'와 소문자 영어 문자가 있는 문자열 s가 있다고 가정합니다. 결과 괄호 문자열이 유효하고 마지막으로 유효한 문자열을 반환해야 하도록 최소 개수의 괄호( '(' 또는 ')', 모든 위치에서)를 삭제해야 합니다. 여기에서 괄호 문자열은 이러한 모든 기준이 충족될 때 유효합니다 -
-
문자열이 비어 있고 소문자만 포함하거나
-
문자열은 A와 B가 유효한 문자열인 AB(A와 B 연결)로 쓸 수 있습니다. 또는
-
문자열은 (A)의 형식으로 작성할 수 있습니다. 여기서 A는 유효한 문자열입니다.
따라서 입력이 s ="m)n(o)p"와 같으면 출력은 "mn(o)p"
가 됩니다.이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
스택 :=새 목록
-
인덱스 :=새로운 세트
-
나는 :=0
-
s의 각 c에 대해
-
c가 '('와 같으면
-
i를 스택에 푸시
-
-
그렇지 않으면 c가 ')'와 같을 때
-
스택의 크기가 0이면
-
인덱스에 i 삽입
-
-
그렇지 않으면
-
스택에서 팝
-
-
나는 :=나는 + 1
-
-
-
ret :=빈 문자열
-
indexes :=모든 요소를 인덱스에 저장
-
범위 0에서 s - 1까지의 i에 대해 수행
-
인덱스에 없으면
-
렛 :=렛 + s[i]
-
-
-
리턴 렛
예시
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
def solve(s):
stack = []
indexes = set()
i = 0
for c in s:
if c == '(':
stack.append(i)
elif c == ')':
if len(stack) == 0:
indexes.add(i)
else:
stack.pop()
i += 1
ret = ''
indexes = indexes.union(stack)
for i in range(len(s)):
if i not in indexes:
ret += s[i]
return ret
s = "m)n(o)p"
print(solve(s)) 입력
"m)n(o)p"
출력
mn(o)p