Short+Simple Java using Strings


  • 134

    Collect the set of things we see, encoded as strings. For example:

    • '4' in row 7 is encoded as "(4)7".
    • '4' in column 7 is encoded as "7(4)".
    • '4' in the top-right block is encoded as "0(4)2".

    Scream false if we ever fail to add something because it was already added (i.e., seen before).

    public boolean isValidSudoku(char[][] board) {
        Set seen = new HashSet();
        for (int i=0; i<9; ++i) {
            for (int j=0; j<9; ++j) {
                if (board[i][j] != '.') {
                    String b = "(" + board[i][j] + ")";
                    if (!seen.add(b + i) || !seen.add(j + b) || !seen.add(i/3 + b + j/3))
                        return false;
                }
            }
        }
        return true;
    }
    

    Edit: Just occurred to me that we can also make it really clear and self-explaining. I'm loving it.

    public boolean isValidSudoku(char[][] board) {
        Set seen = new HashSet();
        for (int i=0; i<9; ++i) {
            for (int j=0; j<9; ++j) {
                char number = board[i][j];
                if (number != '.')
                    if (!seen.add(number + " in row " + i) ||
                        !seen.add(number + " in column " + j) ||
                        !seen.add(number + " in block " + i/3 + "-" + j/3))
                        return false;
            }
        }
        return true;
    }

  • -2
    F

    if the input is:{'.','8','7','6','5','4','3','2','1'},
    {'2','.','.','.','.','.','.','.','.'},
    {'3','.','.','.','.','.','.','.','.'},
    {'4','.','.','.','.','.','.','.','.'},
    {'5','.','.','.','.','.','.','.','.'},
    {'6','.','.','.','.','.','.','.','.'},
    {'7','.','.','.','.','.','.','.','.'},
    {'8','.','.','.','.','.','.','.','.'},
    {'9','.','.','.','.','.','.','.','.'},
    I think the right output should be wrong. But in this solution, it returns true?why?


  • 3

    Read the problem again, particularly the Note section.


  • 0
    L

    so brilliant!


  • 0
    S

    Wow, compared to my solution this is amazingly brilliant. What's the runtime for this solution?


  • 0

    It's 10-11 ms.


  • 2
    V

    Stefan, I am officially your fan now!


  • 4

    Sometimes I prefer "readable" then "effective", love this


  • 0
    R
    This post is deleted!

  • 3

    +1 love it! Readable is the first place!


  • 0
    W

    This is really amazing!!!


  • 0
    C

    Very nice, I love how readable it is especially the second one. Brilliant.


  • 0
    R

    @FancyFan
    I think if we obey the rules of Sudoku,this testcase is wrong.But the question seems not express this.


  • 0
    R

    @FancyFan
    And this problem is only to show how to make sure to let the Sudoku valid but not to let us make an algotithm to filled all the empty cells.So, I think the testcase is true can be understood.


  • 0
    A

    @StefanPochmann The longer the string, the longer it takes to calculate its hash. Besides, every time you search a hash, the library must literally compare the original string character by character to the one stored together with the hash value to make sure it is not a collision. So generally, it is bad to have longer keys.


  • 1

    @ayuanx There are at most 243 strings in the set and they're at most 14 characters long. Also, I don't think speed is an issue here. I think you worry too much :-). But yes, obviously it might be a bad idea if there were many more/longer strings or high speed was critical. I doubt I solved any other LeetCode problem like this, here I only allowed myself to do it because of the fixed small size.


  • 0

    I really like this solution. I don't like my solution of 2 blocks of 2-layer nested 'for' loops and 1 block of 4-layer nested 'for' loops. I learnt a lot from this solution. thanks for sharing. :)


  • 0
    R
    import java.util.HashMap;
    import java.util.Map;
    import java.util.Set;
    import java.util.HashSet;
    import java.util.Arrays;
    import java.util.Collections;
    
    
    public class Solution {
        public boolean isValidSudoku(char[][] board) {
            
            int rows = board.length;
            int cols = board[0].length;
            if (rows != 9 || cols != 9) {
                return false;
            }
            
            Set<String> keys = new HashSet<String>();
            
            for (int i = 0; i < rows; i++) {
                for (int j = 0; j < cols; j++) {
                    
                    if (board[i][j] != '.' && board[i][j] != ' ') {
                        
                        // generate the key
                        String rowKey = getRow(i)+String.valueOf(board[i][j]);
                        String colKey = getCol(j)+String.valueOf(board[i][j]);
                        String sectionKey = getSection(i, j)+String.valueOf(board[i][j]);
                        
                        // check if the key is present
                        if (keys.contains(rowKey) || 
                            keys.contains(colKey) ||
                            keys.contains(sectionKey)) {
                                System.out.println(Arrays.toString(keys.toArray()));
                                System.out.println("Row " + rowKey + " Col " + colKey + " Section " + sectionKey);
                                return false;
                                
                            } else {
                                
                                keys.add(rowKey);
                                keys.add(colKey);
                                keys.add(sectionKey);
                            }
                        
                        // take action
                        
                    }
                        
                    
                    
                    
                }
            }
            
            
            System.out.println(Arrays.toString(keys.toArray()));
            return true;
            
            
        }
        
        public String getRow(int i) {
            return "(row" + i + ")";
        }
        
        public String getCol(int i) {
            return "(col" + i + ")";
        }
        
        
        public String getSection(int row, int col) {
            if ((row >= 0) && (row <= 2)) {
                if (col >= 0 && col <= 2) {
                    return "(Section1)";
                } else if (col >=3 && col <= 5) {
                    return "(Section2)";
                } else {
                    return "(Section3)";
                }
                
            } else if (row >=3 && row <= 5) {
                if (col >= 0 && col <= 2) {
                    return "(Section4)";
                } else if (col >=3 && col <= 5) {
                    return "(Section5)";
                } else {
                    return "(Section6)";
                }
                
            } else {
                // last 3 rows
                if (col >= 0 && col <= 2) {
                    return "(Section7)";
                } else if (col >=3 && col <= 5) {
                    return "(Section8)";
                } else {
                    return "(Section9)";
                }
                
            }
        }
    }
    
    
    
    
    

  • 0
    W

    wow this is cool


  • 0

    Stefan, you are so clever! How could you code in such a way?


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.