leetcode 45(dp), 125(regex), 680(팰린드롬, 구현), 403(dfs)

45 https://leetcode.com/problems/jump-game-ii/

 

설명은 코드에 적는다. dp문제이다.

class Solution:
    def jump(self, nums: List[int]) -> int:
        dp = [99999999]*len(nums)
        dp[0] = 0  # 인덱스 0에서 시작함.
        cur_max = 0
        for i in range(len(nums)):
            if i+nums[i] > cur_max:  # 현재 갈수 있는 최대거리 이상으로 갈수있을때만 루프를 돈다.
                cur_max = i+nums[i]  # 현재 갈수 있는 최대거리 갱신
                for j in range(i+1, min(i+1+nums[i], len(nums))):  # 현 위치에서 갈수있는곳들의 값을 업데이트시켜줌.
                    dp[j] = min(dp[j], dp[i] + 1)
        return dp[-1]

125 https://leetcode.com/problems/valid-palindrome/

 

https://stackoverflow.com/questions/6323296/python-remove-anything-that-is-not-a-letter-or-number

 

정규식으로 지운다.

import re

class Solution(object):
    def isPalindrome(self, s):
        s = re.sub('[\_\W]+', '', s).lower()
        return s == s[::-1]

680 https://leetcode.com/problems/valid-palindrome-ii/

 

팰린드롬의 길이나 그런걸 구하는게 아니라 단순히 팰린드롬을 만들수 있느냐?에 관한 문제이다. 처음에 재귀로 풀었는데 많이 느렸다. flag는 한번 단어를 지울수 있는지 여부를 나타낸다.

class Solution(object):
    def validPalindrome(self, s):
        def check(l, r, flag):
            if l >= r:
                return True
            elif s[l] == s[r]:
                return check(l+1, r-1, flag)
            else:
                if not flag:
                    return False
                ll = check(l+1, r, not flag)
                rr = check(l, r-1, not flag)
                return ll or rr
        
        r = check(0, len(s)-1, True)
        return r

생각해보니까 굳이 계속 재귀할 필요없이 반복문으로 풀면 되었다.

class Solution(object):
    def validPalindrome(self, s):
        def check(l, r, flag):
            while l < r:
                if s[l] == s[r]:
                    l += 1
                    r -= 1
                else:
                    if not flag:
                        return False
                    ll = check(l+1, r, not flag)
                    rr = check(l, r-1, not flag)
                    return ll or rr
            return True
        
        r = check(0, len(s)-1, True)
        return r

근데 또 생각해보니까 딱 한글자만 지우면 되니까 flag란 변수가 필요가 없었다. 재귀도 필요없었다.

class Solution(object):
    def validPalindrome(self, s):
        l, r = 0, len(s)-1
        while l < r:
            if s[l] == s[r]:
                l += 1
                r -= 1
            else:
                ll = s[l+1:r+1] == s[l+1:r+1][::-1]  # 한번 기회가 있으니 l에서 한개 지운후 그자리에서 팰린드롬인지 비교함.
                rr = s[l:r] == s[l:r][::-1]  # 한번 기회가 있으니 r에서 한개 지운후 그자리에서 팰린드롬인지 비교함.
                return ll or rr
        return True

속도가 엄청 줄었다.

 

403 https://leetcode.com/problems/frog-jump/

 

dfs로 푼다.

from collections import deque

class Solution(object):
    def canCross(self, stones):
        stack = deque([[0, [1]]])
        visited = set((0, (1)))
        stone_index = set(stones)
        while stack:
            cur_index, jump_list = stack.pop()
            if cur_index == stones[-1]:
                return True
            for next_jump in jump_list:
                next_index = cur_index + next_jump
                next_next_jump = range(next_jump-1, next_jump+2)
                if (next_index, tuple(next_next_jump)) not in visited and next_index in stone_index:
                    visited.add((next_index, tuple(next_next_jump)))
                    stack.append([next_index, next_next_jump])
        return False