leetcode 79(dfs), 209(two pointer), 718(dp), 9(구현), 70(dp)

79 https://leetcode.com/problems/word-search/

dfs로 푼다.

from collections import deque

class Solution(object):
    def exist(self, board, word):
        #board = [["A","B","C","E"],
        #         ["S","F","E","S"],
        #         ["A","D","E","E"]]
        #word = "ABCESEEEFS"
        #board = [["A","B","C","E"],
        #         ["S","F","C","S"],
        #         ["A","D","E","E"]]
        #word = "ABCB"
        
        queue = deque()
        row_len = len(board)
        col_len = len(board[0])
        
        for i in xrange(row_len):
            for j in xrange(col_len):
                if board[i][j] == word[0]:
                    queue.append([i, j, set([col_len*i + j]), word[1:]])  # [x좌표, y좌표, visited, 방문해야하는 남은 단어들]
                    
        while queue:
            cur_row, cur_col, visited, must_visit = queue.pop()
            if len(must_visit) == 0:  # 다 방문했으면 return
                return True
            for idx in [[-1, 0], [0, -1], [0, 1], [1, 0]]:
                next_row = cur_row + idx[0]
                next_col = cur_col + idx[1]
                if not (0 <= next_row < row_len) or not (0 <= next_col < col_len):  # 다음 좌표가 하나라도 벗어났으면 continue
                    continue
                
                if board[next_row][next_col] == must_visit[0] and (col_len * next_row + next_col) not in visited:  # 다음 좌표의 단어가 다음 단어면서 방문한적이 없어야 함.
                    queue.append([next_row, next_col, visited | set([col_len * next_row + next_col]), must_visit[1:]])
        return False

209 https://leetcode.com/problems/minimum-size-subarray-sum/

전형적인 투 포인터 문제.

class Solution(object):
    def minSubArrayLen(self, s, nums):
        if not nums:
            return 0
        l, r = 0, 0
        _sum = 0
        ret = 99999999999
        while r < len(nums):
            _sum += nums[r]
            while _sum >= s:
                ret = min(ret, r - l + 1)
                _sum -= nums[l]
                l += 1
            r += 1
        return ret if ret != 99999999999 else 0

718 https://leetcode.com/problems/maximum-length-of-repeated-subarray/

dp 기본

class Solution(object):
    def findLength(self, A, B):
        dp = [[0]*len(B) for i in xrange(len(A))]
        for i in xrange(len(A)):
            for j in xrange(len(B)):
                if A[i] == B[j]:
                    prev = 0 if i == 0 or j == 0 else dp[i-1][j-1]
                    dp[i][j] = prev + 1
                    
        return max(map(max, dp))

9 https://leetcode.com/problems/palindrome-number/

설명이 필요 없다.

class Solution(object):
    def isPalindrome(self, x):
        if x < 0:
            return False
        
        ret = []
        while x > 0:
            ret.append(x % 10)
            x /= 10
            
        for i in xrange(len(ret)/2):
            if ret[i] != ret[len(ret)-1-i]:
                return False
        return True

70 https://leetcode.com/problems/climbing-stairs/

dp 초기초문제.

class Solution(object):
    def climbStairs(self, n):
        if n < 3:
            return n
        dp = [0]*(n+1)
        dp[1] = 1
        dp[2] = 2
        for i in xrange(3, n+1):
            dp[i] = dp[i-1] + dp[i-2]
        return dp[n]