1614. Maximum Nesting Depth of the Parentheses

leetcode.com/problems/maximum-nesting-depth-of-the-parentheses/

    def maxDepth(self, s):
        res = cur = 0
        for c in s:
            if c == '(':
                cur += 1
                res = max(res, cur)
            if c == ')':
                cur -= 1
        return res

괄호문제는 보통 스택이 필요할것 같지만, 잘 생각해보면 필요없다.

그리고 아래의 조건 때문에, 짝이 안맞는것을 디텍팅할 필요도 없다. 문제를 잘 읽자.

For example, "", "()()", and "()(()())" are VPS's (with nesting depths 0, 1, and 2), and ")(" and "(()" are not VPS's.

Given a VPS represented as string s, return the nesting depth of s.

More Parentheses Problem To Advance

Here is a ladder of parentheses problem, in order of problem number.

1. Minimum Insertions to Balance a Parentheses String
1. Minimum Remove to Make Valid Parentheses
1. Maximum Nesting Depth of Two Valid Parentheses Strings
1. Reverse Substrings Between Each Pair of Parentheses
1. Remove Outermost Parentheses
1. Minimum Add to Make Parentheses Valid
1. Score of Parentheses

1615. Maximal Network Rank

leetcode.com/problems/maximal-network-rank/

코드 개선을 좀 해야할듯

class Solution:
    def maximalNetworkRank(self, n: int, roads: List[List[int]]) -> int:
        connected = collections.defaultdict(set)
        for a, b in roads:
            connected[a].add(b)
            connected[b].add(a)
        M = 0
        for i in range(n):
            for j in range(i + 1, n):
                M = max(M, len(connected[i]) + len(connected[j]) - (i in connected[j]))
        return M

엄청빠른코드

class Solution:
    def maximalNetworkRank(self, n: int, roads: List[List[int]]) -> int:
        if n == 0 or len(roads) == 0:
            return 0
        
        d = [0 for i in range(0,n)]
            
        for road in roads:
            d[road[0]] += 1
            d[road[1]] += 1
        
        first = -1
        second = -1
        
        for degree in d:
            if first <= degree:
                second = first
                first = degree
            elif second < degree:
                second = degree
        
        _d = {}
        for i in range(0,len(d)):
            if second <= d[i]:
                _d[i] = 0
        
        for road in roads:
            if road[0] in _d and road[1] in _d:
                _d[road[0]] += 1
                _d[road[1]] += 1
        
        dis = len(_d) - 1
        toret = first + second -1
        for k,v in _d.items():
            if first == d[k]:
                if v == min(dis, d[k]):
                    continue
                else:
                    toret += 1
                    break
        
        #print(_d)
        #print(d[4],d[16],d[30])
        
        return toret

1616. Split Two Strings to Make Palindrome

leetcode.com/problems/split-two-strings-to-make-palindrome/

구글기출

Try finding the largest prefix form a that matches a suffix in b

Try string matching

result 에서 빠른 알고리즘들은 전부 틀린거였다.

여깃부터 맞는것

class Solution:
    def checkPalindromeFormation(self, a: str, b: str) -> bool:
        def check(a, b):
            N = len(a)
            for i in range(N):
                if a[i] != b[i]:
                    break
            if i >= N//2:
                return True
            if a[i:N-i] == a[i:N-i][::-1] or b[i:N-i] == b[i:N-i][::-1]:
                return True
            return False
        return check(a, b[::-1]) or check(b, a[::-1])

class Solution:
    def checkPalindromeFormation(self, a: str, b: str) -> bool:
        def isPan(a):
            return a[::-1]==a
        def check(a,b):
            i,n =0, len(a)
            while i<n and a[i] ==b[~i]:
                i+=1 # i++, j-- this is easier to write
            k= a[i:n-i]
            l =b[i:n-i]
            if isPan(k) or isPan(l):
                return True
            return False
        return check(a,b) or check(b,a)

class Solution:
    
    def check(self, a:str, b:str) -> bool:
        i = 0
        j = len(a)-1
        while i < j and a[i]==b[j]:
            i+=1
            j-=1
       
        return a[i:j+1]==a[i:j+1][::-1] or b[i:j+1]==b[i:j+1][::-1]
        
    def checkPalindromeFormation(self, a: str, b: str) -> bool:
        return self.check(a, b) or self.check (b, a)

class Solution:
    def palin(self, s): 
        return s == s[::-1]
    
    def check(self, a, b):
        l, r = 0, len(a) - 1        
        while l < r and a[l] == b[r]:            
            l += 1
            r -= 1
        return self.palin(a[l:r+1]) or self.palin(b[l:r+1])
    
    def checkPalindromeFormation(self, a: str, b: str) -> bool:        
        return self.check(a, b) or self.check(b, a)

class Solution:
    def checkPalindromeFormation(self, a: str, b: str) -> bool:
        
            
        def pal_center_len(a):
            e = len(a) // 2
            s = e if len(a) % 2 == 1 else e - 1
                
            while s >= 0:
                if a[s] != a[e]:
                    break
                s -= 1
                e += 1
                
            return e - s - 1
        
        
        max_center_len = max(pal_center_len(a), pal_center_len(b))
        if max_center_len == len(a):
            return True
        
        rLen = (len(a) - max_center_len) // 2
        return a[:rLen] == b[:-rLen-1:-1] or b[:rLen] == a[:-rLen-1:-1]

    def checkPalindromeFormation(self, a, b):
        i, j = 0, len(a) - 1
        while i < j and a[i] == b[j]:
            i, j = i + 1, j - 1
        s1, s2 = a[i:j + 1], b[i:j + 1]

        i, j = 0, len(a) - 1
        while i < j and b[i] == a[j]:
            i, j = i + 1, j - 1
        s3, s4 = a[i:j + 1], b[i:j + 1]

        return any(s == s[::-1] for s in (s1,s2,s3,s4))