Function leetcode_for_rust::cd0212_word_search_ii::find_words

pub fn find_words(board: Vec<Vec<char>>, words: Vec<String>) -> Vec<String>

Solutions

Approach : Trie and DFS

• Time complexity:

• Space complexity:

• It doesn't work, I'm sorry

use std::collections::HashSet;

#[derive(Debug, Default)]
pub struct Trie {
    is_end: bool,
    nodes: [Option<Box<Trie>>; 26],
}

impl Trie {

    fn new() -> Self {
        Default::default()
    }

    fn insert(&mut self, word: String) {
        let mut curr = self;
        for i in word.chars().map(|char| (char as u8 - 'a' as u8) as usize) {
            curr = curr.nodes[i].get_or_insert_with(|| Box::new(Trie::new()));
        }
        curr.is_end = true;
    }
}

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

    pub fn find_words(mut board: Vec<Vec<char>>, words: Vec<String>) -> Vec<String> {
        let rows = board.len();
        let cols = board[0].len();

        if rows == 0 || cols == 0 || words.len() == 0 { return vec![]; }

        let mut trie = Trie::new();
        let mut result: HashSet<String> = HashSet::new();

        for word in words { trie.insert(word); }

        for row in 0..rows {
            for col in 0..cols {
                let mut s = String::from("");
                Self::_dfs(&mut board, &mut result, &mut s, row, col, &trie);
            }
        }

        result.into_iter().collect::<Vec<String>>()
    }

    pub fn _dfs(board:  &mut Vec<Vec<char>>,
                result: &mut HashSet<String>,
                s:      &mut String,
                row:    usize,
                col:    usize,
                trie:   &Trie) {
        let mut curr = trie;
        if let Some(node) = trie.nodes[(board[row][col] as u8 - 'a' as u8) as usize].as_ref() {
            curr = node;
            s.push(board[row][col]);
            if curr.is_end { result.insert(s.clone()); }
            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 ni >= board.len() || nj >= board[0].len() || board[ni][nj] == '#' { continue; }

                let ch = board[row][col];
                board[row][col] = '#';
                Self::_dfs(board, result, s, ni, nj, curr);
                board[row][col] = ch;
            }
        }
    }
}