leetcode 244(two pointer), 91(dp), 909(bfs), 16(two pointer)

244 https://leetcode.com/problems/shortest-word-distance-ii/
모든 word의 인덱스를 저장해놓는다. 그리고 구해야 하는 두 점에 대해서 투 포인터로  가장 근접해 있는 점 끼리의 최소값을 업데이트해준다.

class WordDistance:
    def __init__(self, wd: List[str]):
        self.d = {}
        for i, w in enumerate(wd):
            self.d[w] = self.d.get(w, []) + [i]
        #print(self.d)

    def shortest(self, w1: str, w2: str) -> int:
        ret = 9999999999
        i,j = 0,0
        d1,d2 = self.d[w1],self.d[w2]
        while i < len(d1) and j < len(d2):
            ret = min(ret, abs(d1[i] - d2[j]))
            if d1[i] >= d2[j]:  # i가 j보다 더 크면 위치를 최대한 비슷하게 해주기 위해서 j를 증가시켜줌. 반대는 i를 증가.
                j += 1
            else:
                i += 1
        return ret

91 https://leetcode.com/problems/decode-ways/
딱 보자마자 알수있는 dp문제다. 숫자로 만들수 있는 문자의 경우의 수를 구하는 문제이다.

class Solution:
    def numDecodings(self, s: str) -> int:
        #s = '27'
        dp = {}
        def get_alpha(s):
            if s == '':
                return 1
            elif s in dp:
                return dp[s]
            
            ret = 0
            if len(s) > 0 and s[0] != '0':  # s를 쪼개기 위해서는 길이가 1 이상이면서 0으로 시작하면 안된다.
                t1 = get_alpha(s[1:])
                t2 = 0
                if len(s) > 1 and int(s[:2]) <= 26:  # 앞의 두개로 쪼개기 위해서는 길이가 2 이상이면서 2까지의 문자가 26(Z)까지만 허용된다.
                    t2 = get_alpha(s[2:])
                dp[s] = t1 + t2
                ret = dp[s]
            return ret
        return get_alpha(s)

909 https://leetcode.com/problems/snakes-and-ladders/
오랫만에 보는 bfs dfs문제인데 은근히 푸는데 시간이 걸렸다..

from collections import deque

class Solution:
    def snakesAndLadders(self, board: List[List[int]]) -> int:
        n = len(board[0])
        if n % 2 == 0:
            new_board = [board[i][::-1] if i % 2 == 0 else board[i] for i in range(len(board)-1, -1, -1)]
        else:
            new_board = [board[i][::-1] if i % 2 == 1 else board[i] for i in range(len(board)-1, -1, -1)]
        #for b in new_board:
        #    print(b)
        
        visited = set((0, 0))
        queue = deque([[0, 0, 0]])
        ret = []
        while queue:
            row, column, move = queue.popleft()
            if row == column == n-1:
                ret.append(move)
                continue
            for next_step in range(1, min(6, n**2)+1):
                new_row = row
                new_column = column + next_step
                if new_column >= n:
                    new_row += 1
                    if new_row >= n:
                        new_row %= n
                    new_column %= n
                if (new_row, new_column) in visited:
                    continue
                visited.add((new_row, new_column))
                if new_board[new_row][new_column] != -1:
                    new_row, new_column = (new_board[new_row][new_column]-1)//n, (new_board[new_row][new_column]-1)%n
                queue.append([new_row, new_column, move + 1])
        return min(ret) if ret else -1

16 https://leetcode.com/problems/3sum-closest/
바로 전 15번문제인 3 sum https://leetcode.com/problems/3sum/ 에서 조금만 변경하면 된다. https://qkqhxla1.tistory.com/1055 에서 풀었었다.

class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        nums.sort()
        ret = 999999999
        num_len = len(nums)
        for i in range(len(nums)-2):
            l, r = i+1, len(nums)-1
            while l < r:
                total = nums[i] + nums[l] + nums[r]
                if abs(total - target) < abs(ret - target):  # 현 total이 기존것보다 더 가까우면 갱신해줌.
                    ret = total
                if total < target:
                    l += 1
                elif total > target:
                    r -= 1
                else:
                    return target
        return ret