LeetCode 291. Word Pattern II

Problem Statement

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);
    }
}