forked from kamyu104/LeetCode-Solutions
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathcheck-knight-tour-configuration.py
More file actions
30 lines (27 loc) · 1022 Bytes
/
Copy pathcheck-knight-tour-configuration.py
File metadata and controls
30 lines (27 loc) · 1022 Bytes
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
# Time: O(m * n)
# Space: O(m * n)
# hash table, simulation
class Solution(object):
def checkValidGrid(self, grid):
"""
:type grid: List[List[int]]
:rtype: bool
"""
if grid[0][0]:
return False
lookup = [None]*(len(grid)*len(grid[0]))
for i in xrange(len(grid)):
for j in xrange(len(grid[0])):
lookup[grid[i][j]] = (i, j)
return all(sorted([abs(lookup[i+1][0]-lookup[i][0]), abs(lookup[i+1][1]-lookup[i][1])]) == [1, 2] for i in xrange(len(lookup)-1))
# Time: O(m * n)
# Space: O(m * n)
# hash table, simulation
class Solution2(object):
def checkValidGrid(self, grid):
"""
:type grid: List[List[int]]
:rtype: bool
"""
lookup = {grid[i][j]:(i, j) for i in xrange(len(grid)) for j in xrange(len(grid[0]))}
return grid[0][0] == 0 and all(sorted([abs(lookup[i+1][0]-lookup[i][0]), abs(lookup[i+1][1]-lookup[i][1])]) == [1, 2] for i in xrange(len(lookup)-1))