Simple C# DFS search. beat 98%


  • 1

    Using simple types and not using generics helps a lot. I tried using a hashset of tuples to track used items. Performance was bad.

    public bool Exist(char[,] board, string word) {
        int maxRows = board.GetLength(0);
        int maxCols = board.GetLength(1);
        char[] wa = word.ToCharArray();
    
        if (wa.Length == 0)
        {
            return false;    
        }
        
        for(int i = 0; i < maxRows; i++)
        {
            for(int j= 0; j < maxCols; j++)
            {
                if (board[i,j] == wa[0])
                {
                    bool[,] used = new bool[maxRows, maxCols];
                    // Start search from here.
                    bool found = FindWord(i, j, wa, 0, board, used);
                    if (found)
                    {
                        // Exit early.
                        return true;
                    }
                }
            }
        }
        
        return false;
    }
    
    private bool FindWord(int i, int j, char[] wa, int wi, char[,] board, bool[,] used)
    {
        if (wi == wa.Length)
        {
            return true;    
        }
        
        if (i < 0 || i >= board.GetLength(0) || j < 0 || j >= board.GetLength(1) || used[i, j])
        {
            return false;    
        }
        
        if (wa[wi] == board[i,j])
        {
            used[i, j] = true;
            bool found = FindWord(i, j + 1, wa, wi + 1, board, used) || 
            FindWord(i, j - 1, wa, wi + 1, board, used) || 
            FindWord(i + 1, j, wa, wi + 1, board, used) ||
            FindWord(i - 1, j, wa, wi + 1, board, used);
            used[i,j] = false;
            return found;
        }
        
        return false;
    }

  • 1
    W

    This is almost identical to the implementation I had haha. Few things to note:

    • No need to cast the word to a char array, strings can be indexed the same way in C# as a char array
    • Function parameters should be named better than wa/wi/i/j. Better parameters would be x, y, word, wordIndex
    • No need to create a found bool, just do an if on the FindWord call
    • You should probably just instantiate your used 2d array outside the for loop so a new 2d array isn't generated every time the first character in the word is encountered in the board.
    • wi could just be incremented once before all the recursive FindWord calls

  • 0

    Thanks for the feedback. Will keep in mind for the next time.


  • 0
    J

    Out of curiosity, what was your runtime?

    I came up with a nearly exact solution in Ruby and it runs at 249ms. But that is probably just Ruby being Ruby.


  • 0

    @jamesfm - I got 152 ms


Log in to reply
 

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