leetcode 994(bfs), 286(bfs), 5(팰린드롬), 3(sliding window)

994 https://leetcode.com/problems/rotting-oranges/

 

쉬어가는 bfs 비슷한문제.

class Solution(object):
    def orangesRotting(self, grid):
        visited = set()
        def bfs(rotten_index_list):
            queue = rotten_index_list
            while queue:
                pop = queue.pop(0)
                for m in [[-1, 0], [0, 1], [0, -1], [1, 0]]:
                    popx, popy = pop[0] + m[0], pop[1] + m[1]
                    if popx < 0 or popy < 0 or popx > len(grid)-1 or \
                        popy > len(grid[0])-1 or (popx, popy) in visited or \
                        grid[popx][popy] == 0:
                        continue

                    grid[popx][popy] = 2
                    visited.add((popx, popy))
        
        minute = 0
        prev_rotten_index_list = []
        while True:
            rotten_index_list = []
            for i in xrange(len(grid)):
                for j in xrange(len(grid[0])):
                    if grid[i][j] == 2:
                        rotten_index_list.append([i, j])
            if prev_rotten_index_list == rotten_index_list:
                minute -= 1
                break
            
            prev_rotten_index_list = rotten_index_list[:]
            bfs(rotten_index_list)
            minute += 1
            
        for i in xrange(len(grid)):
            for j in xrange(len(grid[0])):
                if grid[i][j] == 1:
                    return -1
        if minute == -1:
            return 0
        return minute

286 https://leetcode.com/problems/walls-and-gates/

 

쉬어가는 bfs문제 2

class Solution(object):
    def wallsAndGates(self, rooms):
        def bfs(x, y):
            queue = [[x, y, 0]]
            visited = set()
            while queue:
                pop = queue.pop(0)
                for m in [[-1, 0], [0, 1], [0, -1], [1, 0]]:
                    popx, popy = pop[0] + m[0], pop[1] + m[1]
                    if popx < 0 or popy < 0 or popx > len(rooms)-1 or \
                        popy > len(rooms[0])-1 or rooms[popx][popy] == -1 or \
                        (popx, popy) in visited:
                        continue
                    visited.add((popx, popy))
                    if pop[2] + 1 < rooms[popx][popy]:
                        rooms[popx][popy] = pop[2] + 1
                        queue.append([popx, popy, pop[2] + 1])
                
        for i in xrange(len(rooms)):
            for j in xrange(len(rooms[0])):
                if rooms[i][j] == 0:
                    bfs(i, j)

5 https://leetcode.com/problems/longest-palindromic-substring/

 

정말 한참을 고민하고 예전 코드도 참조했었다. https://qkqhxla1.tistory.com/745에서 가장 긴 부분문자열 팰린드롬 길이을 구하는 문제가 있었는데 이 코드도 참조하려고 했었다. 풀어보니까 쉬운건데 오랫만에 하니까 머리가 안돌아갔다...

 

근데 문제 조건을 보니 가장 긴 부분문자열 팰린드롬의 길이를 구하는 문제는, s가 100000까지이고, 이 문제는 s의 길이가 1000까지이다. O(n^2)의 시간복잡도로 풀어도 1000000밖에 안되어서 그냥 문제가 시키는대로 O(n^2)로 구현하면 되었다.

class Solution:
    def longestPalindrome(self, s: str) -> str:
        ret = ''
        i = 0
        while i < len(s):
            l = r = i  # 홀수 길이 팰린드롬 최댓값 구하기
            while 0 <= l <= r < len(s) and s[l] == s[r]:
                l -= 1
                r += 1
            
            if len(ret) < r-l:
                ret = s[l+1:r]

            l = i
            r = i+1  # 짝수 길이 팰린드롬 최댓값 구하기
            while 0 <= l <= r < len(s) and s[l] == s[r]:
                l -= 1
                r += 1
            if len(ret) < r-l:
                ret = s[l+1:r]
            #print('2 =',l,r,s[l+1:r])
            i += 1
        return ret

3 https://leetcode.com/problems/longest-substring-without-repeating-characters/

 

슬라이딩 윈도우로 풀수 있다. https://qkqhxla1.tistory.com/1178 같이참조

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        d = {}
        ret = 0
        l, r = 0, 0
        while r < len(s):
            d[s[r]] = d.get(s[r], 0) + 1
            if d[s[r]] > 1:  # 슬라이딩 윈도우의 오른쪽 변수가 이미 한번 나왔었으면 안나올때까지 없애줌.
                while any(d[k] > 1 for k in d.keys()):
                    d[s[l]] -= 1
                    l += 1
            ret = max(ret, r-l+1)
            r += 1
        return ret if ret > 0 else len(s)