use std::collections::HashSet;

impl Solution {
    pub fn min_remove_to_make_valid(s: String) -> String {
        let mut stack = vec![];
        let mut remove = vec![];
        for i in 0..s.len() {
            let c = s.chars().nth(i).unwrap();
            if c == '(' {
                stack.push(i);
            } else if c == ')' {
                if !stack.is_empty() {
                    stack.pop();
                } else {
                    remove.push(i);
                }
            }
        }

        while !stack.is_empty() {
            remove.push(stack.last().unwrap().clone());
            stack.pop();
        }

        let mut ans = "".to_string();
        let set : HashSet<usize> = remove.into_iter().collect();
        for i in 0..s.len() {
            if !set.contains(&i) {
                ans.push(s.chars().nth(i).unwrap());
            }
        }
        return ans;
    }
}

use std::collections::HashSet;

impl Solution {
    pub fn word_break(s: String, word_dict: Vec<String>) -> bool {
        let set: HashSet<String> = word_dict.into_iter().collect();
        let mut dp = vec![false; s.len() + 1];
        dp[0] = true;
        for i in 1..s.len() + 1 {
            if dp[i] {
                continue;
            }
            for j in 0..i {
                if !dp[j] {
                    continue;
                }
                let slice = &s[j..i];
                if set.contains(slice) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[s.len()];
    }
}

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