LeetCode 139. Word Break

Problem Statement

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