LeetCode 140. Word Break II

Problem Statement

use std::collections::HashMap;

impl Solution {
    fn dfs(s:String, word_dict: &Vec<String>, m: &mut HashMap<String, Vec<String>>) -> Vec<String> {
        if m.contains_key(&s) {
            return m.get(&s).unwrap().clone();
        }
        if s.is_empty() {
            return vec!["".to_string()];
        }
        let mut ans = vec![];
        for word in word_dict {
            if s.len() < word.len() || &s[0..word.len()] != word {
                continue;
            }
            let next = &s[word.len()..].to_string().clone();
            let rem = Self::dfs((*next).clone(), word_dict, m);
            for string in rem {
                let mut w = word.clone();
                if !string.is_empty() {
                    w.push(' ');
                }
                w.push_str(&string);
                ans.push(w);
            }
        }
        let ret = ans.clone();
        m.insert(s, ans);
        return ret;
    }

    pub fn word_break(s: String, word_dict: Vec<String>) -> Vec<String> {
        let mut map = HashMap::new();
        return Self::dfs(s, &word_dict, &mut map);
    }
}