문자와 괄호 "(" 및 ")"가 포함된 소문자 문자열이 있다고 가정합니다. 괄호로 묶인 모든 문자열을 재귀적 방식으로 뒤집고 결과 문자열을 반환해야 합니다.
따라서 입력이 s ="back(aps)ce"와 같으면 출력은 "backspace"가 됩니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
함수 trav() 를 정의합니다. 이것은 s, dir, start, close:=close, ans:=ans
가 필요합니다.-
end :="(" dir이 -1과 같으면, 그렇지 않으면 ")"
-
other :="(" 끝이 ")"와 같으면 ")"
-
start
-
s[start]가 other와 같으면
-
trav(s, -dir, 닫기[기타, 시작] - dir)
-
시작 :=닫기[기타, 시작] + 디렉토리
-
-
그렇지 않으면
-
ans의 끝에 s[start] 삽입
-
시작 :=시작 + 디렉토리
-
-
-
-
주 기능에서 다음을 수행하십시오 -
-
ans :=새 목록
-
close :=")" 및 "(" 키를 포함하는 새 맵 처음에 값은 두 개의 빈 맵입니다.
-
스택 :=새 목록
-
s의 각 인덱스 I 및 값 c에 대해 수행
-
c가 "("와 같으면
-
i를 스택에 푸시
-
-
그렇지 않으면 c가 ")"와 같을 때
-
o :=스택의 맨 위, 스택에서 팝
-
닫기[")", i] :=o
-
닫기["(", o] :=i
-
-
-
트래브(들, 1, 0)
-
빈 문자열과 결합하여 반환
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예시
class Solution:
def solve(self, s):
ans = []
close = {")": {}, "(": {}}
stack = []
for i, c in enumerate(s):
if c == "(":
stack.append(i)
elif c == ")":
o = stack.pop()
close[")"][i] = o
close["("][o] = i
def trav(s, dir, start, close=close, ans=ans):
end = "(" if dir == -1 else ")"
other = "(" if end == ")" else ")"
while start < len(s) and s[start] != end:
if s[start] == other:
trav(s, −dir, close[other][start] − dir)
start = close[other][start] + dir
else:
ans.append(s[start])
start += dir
trav(s, 1, 0)
return "".join(ans)
ob = Solution()
print(ob.solve("back(aps)ce")) 입력
"back(aps)ce"
출력
backspace