[Mock] Random 5

---

290. Word Pattern

Given a pattern and a string s, find if s follows the same pattern.

Here follow means a full match, such that there is a bijection between a letter in pattern and a non-empty word in s.

My Answer 1: Accepted (Runtime: 32 ms - 48.26% / Memory Usage: 14.3 MB - 54.71%)

class Solution:
    def wordPattern(self, pattern: str, s: str) -> bool:
        string = s.split()
        dic = {}
        
        if len(pattern) != len(string):
            return False
        
        for i in range(len(pattern)):
            if pattern[i] in dic:
                if dic[pattern[i]] != string[i]:
                    return False
            else:
                if string[i] in dic.values():
                    return False
                dic[pattern[i]] = string[i]
        
        return True

s 는 split 으로 나눠서 string 에 저장하고
pattern 대로 dic 에 저장 => a: dog 이런 식

이미 패턴이 정해진 문자는 기존의 값과 비교해서 다르면 False
패턴이 없는 문자는 새로 넣어주는데 이때, string[i] 가 이미 사용되었는지 확인해주기

• map(s.find, s) == map(t.index, t) 요런거도 가능

---

542. 01 Matrix

Given an m x n binary matrix mat, return the distance of the nearest 0 for each cell.

The distance between two adjacent cells is 1.

My Answer 1: Wrong Answer (13 / 48 test cases passed.)

class Solution:
    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:
        def zero(mat, i, j, n):
            if i < 0 or i >= len(mat) or j < 0 or j >= len(mat):
                return float('inf')
            
            if i - 1 >= 0 and mat[i-1][j] == 0:
                return n+1
            elif i + 1 < len(mat) and mat[i+1][j] == 0:
                return n+1
            elif j - 1 >= 0 and mat[i][j-1] == 0:
                return n+1
            elif j + 1 < len(mat[0]) and mat[i][j+1] == 0:
                return n+1
            else:
                m = float('inf')
                if i - 1 >= 0 and result[i-1][j] != 0:
                    m = min(result[i-1][j] + 1, m)
                elif i + 1 < len(mat) and result[i+1][j] != 0:
                    m = min(result[i+1][j] + 1, m)
                elif j - 1 >= 0 and result[i][j-1] != 0:
                    m = min(result[i][j-1] + 1, m)
                elif j + 1 < len(mat[0]) and result[i][j+1] != 0:
                    m = min(result[i][j+1] + 1, m)
                return m
        
        result = []
        for i in range(len(mat)):
            result.append([0]*len(mat[i]))
        
        for i in range(len(mat)):
            for j in range(len(mat[i])):
                if mat[i][j] == 0:
                    result[i][j] = 0
                else:
                    result[i][j] = zero(mat, i, j, 0)
        
        return result

dp 처럼 누적 distance 를 가져와서 더해가는 걸로 하려고 했는데...
i+1, j+1 의 경우는 미리 확인한 값이 아니라서 안된다는 것을... 뒤늦게 깨달았다...

재귀 써야할 듯

Solution 1: Accepted (Runtime: 524 ms - 96.71% / Memory Usage: 16.2 MB - 98.15%)

class Solution:
    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:
        m, n = len(mat), len(mat and mat[0])
        for i in range(m):
            for j in range(n):
                if mat[i][j] != 0:
                    mat[i][j] = float("inf")
                    if i > 0 and mat[i - 1][j] + 1 < mat[i][j]:
                        mat[i][j] = mat[i - 1][j] + 1
                    if j > 0 and mat[i][j - 1] + 1 < mat[i][j]:
                        mat[i][j] = mat[i][j - 1] + 1
        for i in range(m - 1, -1, -1):
            for j in range(n - 1, -1, -1):
                if mat[i][j] != 0:
                    if i + 1 < m and mat[i + 1][j] + 1 < mat[i][j]:
                        mat[i][j] = mat[i + 1][j] + 1
                    if j + 1 < n and mat[i][j + 1] + 1 < mat[i][j]:
                        mat[i][j] = mat[i][j + 1] + 1
        return mat

가장 이해하기 쉬웠던 루션이.. BFS
따로 변수 선언 없이 그냥 mat 로 끝냄

우선 값이 1 이면 i-1, j-1 값들에 1 을 더해줌

그러고 아까 만났던 문제 해결을 위해서..
뒤에서부터 쭉 보면서 i+1, j+1 을 기반으로 다시 업데이트 => 최솟값일 때만

재귀가 더 복잡한가보다... 잘 안보임
큐나 덱 쓰는 게 많은데 뭔소린지 하나도 모르겠음
그냥 이걸로 외우는 걸로^^