leetcode

Set Matrix Zeroes

Set Matrix Zeroes

O(1) Space Version - 92ms

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Solution:
    def setZeroes(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: void Do not return anything, modify matrix in-place instead.
        """
        m = len(matrix)
        if m == 0:
            return
        n = len(matrix[0])
        row_zero = False
        for i in range(m):
            if matrix[i][0] == 0:
                row_zero = True
        col_zero = False
        for j in range(n):
            if matrix[0][j] == 0:
                col_zero = True
        for i in range(1, m):
            for j in range(1, n):
                if matrix[i][j] == 0:
                    matrix[i][0] = 0
                    matrix[0][j] = 0
        for i in range(1, m):
            if matrix[i][0] == 0:
                for j in range(1, n):
                    matrix[i][j] = 0
        for j in range(1, n):
            if matrix[0][j] == 0:
                for i in range(1, m):
                    matrix[i][j] = 0
        if col_zero:
            for j in range(n):
                matrix[0][j] = 0
        if row_zero:
            for i in range(m):
                matrix[i][0] = 0

test code

1
2
3
4
5
6
In [23]: m = [[1,1,1],[1,0,1],[1,1,1]]
In [24]: s = Solution(); s.setZeroes(m)
In [25]: m
Out[25]: [[1, 0, 1], [0, 0, 0], [1, 0, 1]]

leet code

leetcode

Palindrome Partitioning

Palindrome Partitioning

DFS Version - 192ms

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def partition(self, s):
        """
        :type s: str
        :rtype: List[List[str]]
        """
        res = []
        self.dfs(s, [], res)
        return res
    def dfs(self, s, path, res):
        if not s:
            res.append(path)
            return
        for i in range(1, len(s) + 1):
            if self.is_palindrome(s[:i]):
                self.dfs(s[i:], path + [s[:i]], res)
    def is_palindrome(self, s):
        return s == s[::-1]

test code

1
2
In [10]: s = Solution(); t = s.partition("aab"); print(t)
[['a', 'a', 'b'], ['aa', 'b']]

leet code

leetcode

Longest Increasing Path in a Matrix

Longest Increasing Path in a Matrix

DP Version - 260ms

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def longestIncreasingPath(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: int
        """
        def dfs(i, j):
            if not dp[i][j]:
                val = matrix[i][j]
                dp[i][j] = 1 + max(dfs(i - 1, j) if i and val > matrix[i - 1][j] else 0,
                    dfs(i + 1, j) if i < M - 1 and val > matrix[i + 1][j] else 0,
                    dfs(i, j - 1) if j and val > matrix[i][j - 1] else 0,
                    dfs(i, j + 1) if j < N - 1 and val > matrix[i][j + 1] else 0)
            return dp[i][j]
        if not matrix or not matrix[0]: return 0
        M, N = len(matrix), len(matrix[0])
        dp = [[0] * N for i in range(M)]
        return max(dfs(x, y) for x in range(M) for y in range(N))

test code

1
2
In [7]: s = Solution(); t = s.longestIncreasingPath([[9,9,4],[6,6,8],[2,1,1]]); print(t)
4

leet code

leetcode

Count and Say

Count and Say

groupby Version - 40ms

1
2
3
4
5
6
7
8
9
10
11
import itertools
class Solution:
    def countAndSay(self, n):
        """
        :type n: int
        :rtype: str
        """
        ret = '1'
        for _ in range(n - 1):
            ret = ''.join(str(len(list(group))) + digit for digit, group in itertools.groupby(ret))
        return ret

Prev Version - 52ms

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def countAndSay(self, n):
        """
        :type n: int
        :rtype: str
        """
        ret = '1'
        for _ in range(n - 1):
            prev = ret
            ret = ''
            j = 0
            while j < len(prev):
                cur = prev[j]
                cnt = 1
                j += 1
                while j < len(prev) and prev[j] == cur:
                    cnt += 1
                    j += 1
                ret += str(cnt) + str(cur)
        return ret

test code

1
2
In [472]: s = Solution(); t = s.countAndSay(8); print(t)
1113213211

leet code

leetcode

Number of Islands

Number of Islands

DFS Version - 148ms

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution:
    def numIslands(self, grid):
        """
        :type grid: List[List[str]]
        :rtype: int
        """
        if not grid:
            return 0
        count = 0
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == '1':
                    self.dfs(grid, i, j)
                    count += 1
        return count
    def dfs(self, grid, i, j):
        if i<0 or j<0 or i>=len(grid) or j>=len(grid[0]) or grid[i][j] != '1':
            return
        grid[i][j] = '#'
        self.dfs(grid, i+1, j)
        self.dfs(grid, i-1, j)
        self.dfs(grid, i, j+1)
        self.dfs(grid, i, j-1)

DFS Map Version - 116ms

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def numIslands(self, grid):
        """
        :type grid: List[List[str]]
        :rtype: int
        """
        def sink(i, j):
            if 0 <= i < len(grid) and 0 <= j < len(grid[i]) and grid[i][j] == '1':
                grid[i][j] = '0'
                list(map(sink, (i+1, i-1, i, i), (j, j, j+1, j-1)))
                return 1
            return 0
        return sum(sink(i, j) for i in range(len(grid)) for j in range(len(grid[i])))

test code

1
2
3
4
In [429]: n = [["1","1","1","1","0"],["1","1","0","1","0"],["1","1","0","0","0"],["0","0","0","0","0"]]
In [430]: s = Solution(); t = s.numIslands(n); print(t)
1

leet code