<div id="readability-page-1" class="page"><div><a href="https://leetcode.com/problems/longest-valid-parentheses/" target="_blank" rel="nofollow noopener noreferrer">https://leetcode.com/problems/longest-valid-parentheses/</a>
더 멋있는 풀이는 인터넷에 찾아보시면 많은데… 간단히 하려면 이렇게 할 수도 있다 싶어서 정리해본다.
백그라운드가 PS에 없는지라 남한테 설명이 쉬운 풀이 밖에 못한다 ㅜㅜ;
<div data-language="python"><pre><code>class Solution:
 def longestValidParentheses(self, s: str) -&gt; int:

 
 valid_chars = [False for _ in s]
 
 stack = []
 for i in range(0, len(s)):
 c = s[i]
 if c == '(':
 stack.append(i)
 elif c == ')' and len(stack) != 0:
 matching_i = stack.pop()
 valid_chars[i] = True
 valid_chars[matching_i] = True
 elif c == ')' and len(stack) == 0:
 pass
 
 longest_valid =0 
 current_valid = 0
 for c in valid_chars:
 if c:
 current_valid += 1
 else:
 longest_valid = max(current_valid, longest_valid)
 current_valid = 0
 
 longest_valid = max(current_valid, longest_valid)
 
 return longest_valid</code></pre></div>
스트링에서 ’(‘가 valid한 parentheses가 되려면 나중에 ’)‘를 만나서 괄호가 닫혀야 한다.
그래서 스택을 가지고 원패스로 스트링을 돌면서 각 글자의 validity 여부를 적어놓는다.
그 다음은 이제 다시 저 validity 리스트를 가지고 그중에서 가장 긴 streak의 길이를 구한다.</div></div>

Blog by Hyeungshik Jung

https://leetcode.com/problems/longest-valid-parentheses/
더 멋있는 풀이는 인터넷에 찾아보시면 많은데… 간단히 하려면 이렇게 할 수도 있다 싶어서 정리해본다.
백그라운드가 PS에 없는지라 남한테 설명이 쉬운 풀이 밖에 못한다 ㅜㅜ;
class Solution:
    def longestValidParentheses(self, s: str) -> int:
        
        valid_chars = [False for _ in s]
        
        stack = []
        for i in range(0, len(s)):
            c = s[i]
            if c == '(':
                stack.append(i)
            elif c == ')' and len(stack) != 0:
                matching_i = stack.pop()
                valid_chars[i] = True
                valid_chars[matching_i] = True
            elif c == ')' and len(stack) == 0:
                pass
        
        longest_valid =0 
        current_valid = 0
        for c in valid_chars:
            if c:
                current_valid += 1
            else:
                longest_valid = max(current_valid, longest_valid)
                current_valid = 0
    
        longest_valid = max(current_valid, longest_valid)
        
        return longest_valid
스트링에서 ’(‘가 valid한 parentheses가 되려면 나중에 ’)‘를 만나서 괄호가 닫혀야 한다.
그래서 스택을 가지고 원패스로 스트링을 돌면서 각 글자의 validity 여부를 적어놓는다.
그 다음은 이제 다시 저 validity 리스트를 가지고 그중에서 가장 긴 streak의 길이를 구한다.

Longest valid parentheses

댓글