word break

jhideki · jhideki · commit c7ebef0642f2 · 2024-07-02T14:50:35.000-07:00
diff --git a/src/main.rs b/src/main.rs
@@ -1,2 +1,2 @@
-mod max_prod_subarray;
+mod word_break;
 fn main() {}
diff --git a/src/word_break.rs b/src/word_break.rs
@@ -0,0 +1,18 @@
+pub struct Solution {}
+impl Solution {
+    pub fn word_break(s: String, word_dict: Vec<String>) -> bool {
+        let mut map = vec![false; word_dict.len() + 1];
+        map[word_dict.len() as usize] = true;
+        for i in (0..word_dict.len()).rev() {
+            for word in &word_dict {
+                if i + word.len() <= s.len() && &s[i..i + word.len()] == word {
+                    map[i] = map[i + word.len()];
+                }
+                if map[i] {
+                    break;
+                }
+            }
+        }
+        return map[0];
+    }
+}
