Function leetcode_for_rust::cd0079_word_search::exist

pub fn exist(board: Vec<Vec<char>>, word: String) -> bool

Solutions

Approach 1: DFS

• Time complexity:

• Space complexity:

• Runtime: 8 ms

• Memory: 3.5 MB

impl Solution {
    const DIRS: [[i32; 2]; 4] = [[1, 0], [-1, 0], [0, 1], [0, -1]];

    pub fn exist(mut board: Vec<Vec<char>>, word: String) -> bool {
        if board.is_empty() || board[0].is_empty() { return false; }
        if word.is_empty() { return true; }

        let m = board.len();
        let n = board[0].len();
        let word: Vec<char> = word.chars().collect();
        let mut used = vec![vec![false; n]; m];

        for i in 0..m {
            for j in 0..n {
                if Self::dfs(&board, &word, &mut used, i, j) { return true; }
            }
        }

        false
    }

    pub fn dfs(board: &Vec<Vec<char>>,
               word:  &[char],
               used:  &mut Vec<Vec<bool>>,
               i:     usize,
               j:     usize) -> bool {
        if i >= board.len() || j >= board[0].len() || used[i][j] { return false; }

        if board[i][j] != word[0] { return false; }
        if word.len() == 1 { return true; }

        used[i][j] = true;
        for d in Self::DIRS.iter() {
            let ni = (i as i32 + d[0]) as usize;
            let nj = (j as i32 + d[1]) as usize;
            if Self::dfs(board, &word[1..], used, ni, nj) { return true; }
        }
        used[i][j] = false;
        false
    }
}

Approach 2: DFS

• Time complexity:

• Space complexity:

• Runtime: 8 ms

• Memory: 3.4 MB

impl Solution {
    const DIRS: [[i32; 2]; 4] = [[1, 0], [-1, 0], [0, 1], [0, -1]];

    pub fn exist(mut board: Vec<Vec<char>>, word: String) -> bool {
        let (height, width) = (board.len(), board[0].len());
        if height == 0 || width == 0 || word.len() < 1 { return false }
        let seq: Vec<char> = word.chars().collect();

        for row in 0..height {
            for col in 0..width {
                if board[row][col] == seq[0] && Self::dfs(&mut board, &seq, row, col, 0) {
                    return true
                }
            }
        }
        false
    }

    fn dfs(board: &mut Vec<Vec<char>>, seq: &[char], row: usize, col: usize, count: i32) -> bool {
        if count == seq.len() as i32 { return true; }
        if row >= board.len() || col >= board[0].len() || board[row][col] != seq[count as usize] { return false; }

        let ch = board[row][col];
        board[row][col] = '#';
        for d in Self::DIRS.iter() {
            let ni = (row as i32 + d[0]) as usize;
            let nj = (col as i32 + d[1]) as usize;
            if Self::dfs(board, seq, ni, nj, count+1) { return true; }
        }
        board[row][col] = ch;
        false
    }
}