[LeetCode解題攻略] 36. Valid Sudoku

問題描述

給定一個 9x9 的數獨棋盤，請驗證這個棋盤是否有效。

數獨棋盤需滿足以下條件：

1. 每一行只能包含數字 1-9，不能重複。
2. 每一列只能包含數字 1-9，不能重複。
3. 每一個 3x3 的子方格只能包含數字 1-9，不能重複。

• 數獨棋盤中空格由 '.' 表示。
• 不需要檢查是否可以解出這個數獨，只需要驗證數獨是否有效。

範例 1

輸入：
board = 
[["5","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]
,["4",".",".","8",".","3",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]
,[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]
輸出：true

範例 2

輸入：
board = 
[["8","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]
,["4",".",".","8",".","3",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]
,[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]
輸出：false
解釋：第一列有兩個 8，因此這個棋盤是無效的。

解法一：使用集合檢查每一行、每一列和每個子方格

思路

我們可以將數獨棋盤視為三部分來驗證：

1. 每一行是否有重複數字。
2. 每一列是否有重複數字。
3. 每一個 3x3 子方格是否有重複數字。

對於每部分，我們可以使用 集合 來檢查是否有重複數字：

• 如果某數字已經存在於集合中，則表示有重複，棋盤無效。
• 如果某位置是 '.'，則忽略。

程式碼

class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        rows = [set() for _ in range(9)]
        cols = [set() for _ in range(9)]
        boxes = [set() for _ in range(9)]
        
        for i in range(9):
            for j in range(9):
                num = board[i][j]
                if num == '.':
                    continue
                
                # 檢查行
                if num in rows[i]:
                    return False
                rows[i].add(num)
                
                # 檢查列
                if num in cols[j]:
                    return False
                cols[j].add(num)
                
                # 檢查子方格
                box_index = (i // 3) * 3 + (j // 3)
                if num in boxes[box_index]:
                    return False
                boxes[box_index].add(num)
        
        return True

時間與空間複雜度

• 時間複雜度：O(1)
  數獨棋盤大小固定為 9x9，因此無論如何最多遍歷 81 個格子，時間複雜度為常數。
• 空間複雜度：O(1)
  使用了三個長度為 9 的集合來存儲行、列和子方格的數字，總空間需求固定。

解法二：壓縮空間版本

思路

我們可以用 唯一標識符 來壓縮存儲需求，僅用一個集合來記錄每個數字是否出現過。

1. 將每個數字出現的條件轉化為字串標識，例如：
2. • 數字 5 出現在第 0 行，標識為 "5 in row 0"。
   • 數字 5 出現在第 1 列，標識為 "5 in col 1"。
   • 數字 5 出現在子方格 (0,0)，標識為 "5 in box 0-0"。
2. 將這些標識存入集合，如果發現重複標識則返回 False。

程式碼

class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        seen = set()
        for i in range(9):
            for j in range(9):
                num = board[i][j]
                if num == '.':
                    continue
                
                row_key = f"{num} in row {i}"
                col_key = f"{num} in col {j}"
                box_key = f"{num} in box {i//3}-{j//3}"
                
                if row_key in seen or col_key in seen or box_key in seen:
                    return False
                
                seen.add(row_key)
                seen.add(col_key)
                seen.add(box_key)
        
        return True

時間與空間複雜度

• 時間複雜度：O(1)
  同樣固定遍歷 81 個格子。
• 空間複雜度：O(1)
  由於最多存儲 81 條標識（每個數字最多三條標識），空間需求仍然是固定的。

解法三：逐步檢查行、列、子方格

思路

1. 檢查每一行：將每一行的數字存入集合，檢查是否有重複。
2. 檢查每一列：同樣將每一列的數字存入集合，檢查是否有重複。
3. 檢查每個子方格：對每個子方格中的數字進行檢查。

這種方法較為直觀，分開處理每部分。

程式碼

class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        def isValidSet(values):
            nums = [v for v in values if v != '.']
            return len(nums) == len(set(nums))
            
        # 檢查行
        for row in board:
            if not isValidSet(row):
                return False
        
        # 檢查列
        for col in zip(*board):
            if not isValidSet(col):
                return False
        
        # 檢查子方格
        for i in range(0, 9, 3):
            for j in range(0, 9, 3):
                box = [board[x][y] for x in range(i, i + 3) for y in range(j, j + 3)]
                if not isValidSet(box):
                    return False
        
        return True

時間與空間複雜度

• 時間複雜度：O(1)
  固定遍歷 81 個格子，且每次檢查集合操作為常數時間。
• 空間複雜度：O(1)
  每次檢查時僅臨時存儲數字，無額外存儲需求。

結論

1. 最佳解法：解法二（壓縮空間版本），僅用一個集合，實現簡潔且高效。
2. 其他解法：對於初學者，解法一 和 解法三 更容易理解。
3. 此題重點在於如何高效檢查每一行、每一列與每個子方格是否符合規範，並通過集合實現唯一性檢查。