aboutsummaryrefslogtreecommitdiff
path: root/other/string_compression2.rs
diff options
context:
space:
mode:
Diffstat (limited to 'other/string_compression2.rs')
-rw-r--r--other/string_compression2.rs54
1 files changed, 0 insertions, 54 deletions
diff --git a/other/string_compression2.rs b/other/string_compression2.rs
deleted file mode 100644
index 792a0ac..0000000
--- a/other/string_compression2.rs
+++ /dev/null
@@ -1,54 +0,0 @@
-struct Solution;
-
-impl Solution {
- pub fn get_length_of_optimal_compression(s: String, k: i32) -> i32 {
- #[inline]
- fn len_of_chars(n: i32) -> i32 {
- match n {
- 1 => 1,
- 2..=9 => 2,
- 10..=99 => 3,
- _ => 4,
- }
- }
- fn dfs(v: &[u8], dp: &mut [[i32; 101]; 101], left: i32, k_s: i32) -> i32 {
- let mut k = k_s;
- if v.len() as i32 - left <= k {
- return 0;
- }
- if dp[left as usize][k as usize] >= 0 {
- return dp[left as usize][k as usize];
- }
- let mut ans = if k > 0 {
- dfs(v, dp, left + 1, k - 1)
- } else {
- std::i32::MAX
- };
- let mut c = 1;
- for i in left + 1..=v.len() as i32 {
- ans = ans.min(dfs(v, dp, i, k) + len_of_chars(c));
- if i == v.len() as i32 {
- break;
- }
- if v[i as usize] == v[left as usize] {
- c += 1;
- } else {
- k -= 1;
- if k < 0 {
- break;
- }
- }
- }
- dp[left as usize][k_s as usize] = ans;
- ans
- }
- let mut dp = [[-1; 101]; 101];
- let v = s.as_bytes();
- dfs(v, &mut dp, 0, k)
- }
-}
-
-fn main() {
- let s = String::from("aaabcccd");
- print!("{}", Solution::get_length_of_optimal_compression(s, 2));
-}