36. Valid Sudoku

Problem

Bạn cần kiểm ta xem bảng sudoku đã cho có hợp lệ không, dựa trên 3 quy tắc:

Mỗi hàng chỉ chứa các số từ 1→9, không lặp lại

Mỗi cột chỉ chứa các số từ 1→9, không lặp lại

Mỗi khối 3x3 chỉ chứa các số 1→9, không lặp lại

Approach

Duyệt từng ô trên bảng

Nếu ô không rỗng, khác (’’), kiểm tra xem số này đã xuất hiện ở hàng, cột hoặc khối 3x3 tương ứng chưa

Nếu đã xuất hiện, return false

Nếu chưa, đánh dấu số này đã xuất hiện ở hàng, cột, khối 3x3

Nếu duyệt hết mà không phát hiện trùng lặp, return true

💡

Cách tối ưu là dùng một Set để lưu các chuỗi biểu diễn số đã xuất hiện ở hàng/cột/khối, ví dụ "5 in row 0", "5 in col 1", "5 in block 0-2".

Time and space complexity:

TC: O(n^2), với n là 9

Solution

typescripttypescript

1function isValidSudoku(board: string[][]): boolean {
2    const seen: Set<string> = new Set();
3    for(let i =0; i < 9; i++) {
4	    for(let j =0; j < 9; j++) {
5		    const num = board[i][j];
6		    if(num !== '.') {
7			    const row = num + 'in row' + i;
8			    const col = num + 'in col' + j;
9			    const block = num + 'in block' + Math.floor(i/3) + '-' + Math.floor(j/3);
10			    
11			    if(seen.has(row) || seen.has(col) || seen.has(block)) {
12				    return false;
13			    }
14			    
15			    seen.add(row);
16			    seen.add(col);
17			    seen.add(block);
18		    }
19	    }
20    }
21    
22    return true;
23};

💡

Giải thích

Duyệt toàn bộ bảng với hai vòng lặp i, j

Nếu gặp số, tạo 3 chuỗi đại diện cho vị trí đó ở hàng, cột, khối

Nếu chuỗi nào đã tồn tại trong Set, return false

Nếu không, thêm vào set để đánh dấu đã xuất hiện

Duyệt hết mà không phát hiện trùng lặp thì return true

Loading content...

36. Valid Sudoku

Related Posts

Related Posts

36. Valid Sudoku

Related Posts

2. Add Two Numbers

3. Longest Substring Without Repeating Characters

3. Longest Substring Without Repeating Characters

4. Median of Two Sorted Arrays

5. Longest Palindromic Substring

6. Zigzag Conversion

9. Palindrome Number

11. Container With Most Water

12. Integer to Roman

13. Roman to Integer

14. Longest Common Prefix

17. Letter Combinations of a Phone Number

19. Remove Nth Node From End of List

20. Valid Parentheses

21. Merge Two Sorted Lists

Related Posts

2. Add Two Numbers

3. Longest Substring Without Repeating Characters

3. Longest Substring Without Repeating Characters

4. Median of Two Sorted Arrays

5. Longest Palindromic Substring

6. Zigzag Conversion

9. Palindrome Number

11. Container With Most Water

12. Integer to Roman

13. Roman to Integer

14. Longest Common Prefix

17. Letter Combinations of a Phone Number

19. Remove Nth Node From End of List

20. Valid Parentheses

21. Merge Two Sorted Lists