use std::collections::HashMap;

impl Solution {
    fn dfs(grid: &mut Vec<Vec<char>>, x: i32, y: i32) {
        let (m, n) = (grid.len(), grid[0].len());
        let (dx, dy) = ([1, -1, 0, 0], [0, 0, 1, -1]);
        for i in 0..4 {
            let (xx, yy) = (x + dx[i], y + dy[i]);
            if xx < 0 || xx >= m as i32 || yy < 0 || yy >= n as i32 ||
                grid[xx as usize][yy as usize] == '0' {
                continue;
            }
            grid[xx as usize][yy as usize] = '0';
            Self::dfs(grid, xx, yy);
        }
    }
    pub fn num_islands(grid: Vec<Vec<char>>) -> i32 {
        if grid.is_empty() {
            return 0;
        }
        let mut g = grid.clone();
        let (m, n, mut ans) = (grid.len(), grid[0].len(), 0);
        
        for i in 0..m {
            for j in 0..n {
                if g[i][j] == '1' {
                    ans += 1;
                    Self::dfs(&mut g, i as i32, j as i32);
                }
            }
        }

        return ans;
    }
}

use std::collections::HashMap;

impl Solution {
    pub fn word_pattern(pattern: String, str: String) -> bool {
        let inputs = str.split_whitespace().collect::<Vec<&str>>();
        if pattern.len() != inputs.len() {
            return false;
        }
        let (mut m0, mut m1) = (HashMap::new(), HashMap::new());
        for i in 0..pattern.len() {
            let char = pattern.chars().nth(i).unwrap();
            if !m0.contains_key(&char) {
                m0.insert(char, inputs[i].clone());
            } else {
                if *m0.get(&char).unwrap() != inputs[i] {
                    return false;
                }
            }

            if !m1.contains_key(&inputs[i]) {
                m1.insert(inputs[i].clone(), char);
            } else {
                if *m1.get(&inputs[i]).unwrap() != char {
                    return false;
                }
            }
        }

        return true;
    }
}

use std::collections::HashMap;

impl Solution {
    fn dfs(pattern: &String, string: &String, i: usize, j: usize,
           w2p: &mut HashMap<String, char>, p2w: &mut HashMap<char, String>) -> bool {
        let mut matching = false;
        if i == pattern.len() && j == string.len() {
            return true;
        }
        if i < pattern.len() && j < string.len() {
            let p = pattern.chars().nth(i).unwrap();
            if p2w.contains_key(&p) {
                let w = p2w.get(&p).unwrap();
                let end = std::cmp::min(j + w.len(), string.len());
                let slice = &string[j..end].to_string();
                if *w == *slice {
                    return Self::dfs(pattern, string, i + 1, j + w.len(), w2p, p2w);
                } else {
                    return false;
                }
            } else {
                for k in j..string.len() {
                    if matching {
                        break;
                    }
                    let w = &string[j..k + 1].to_string();
                    if !w2p.contains_key(w) {
                        w2p.insert((*w).to_string(), p);
                        p2w.insert(p, (*w).to_string());
                        matching = Self::dfs(pattern, string, i + 1, k + 1, w2p, p2w);
                        w2p.remove(w);
                        p2w.remove(&p);
                    }
                }
                return matching;
            }
        }
        return false;
    }

    pub fn word_pattern_match(pattern: String, str: String) -> bool {
        let (mut w2p, mut p2w) = (HashMap::new(), HashMap::new());
        return Self::dfs(&pattern, &str, 0, 0, &mut w2p, &mut p2w);
    }
}