diff options
Diffstat (limited to 'string_compression2.rs')
-rw-r--r-- | string_compression2.rs | 54 |
1 files changed, 0 insertions, 54 deletions
diff --git a/string_compression2.rs b/string_compression2.rs deleted file mode 100644 index 792a0ac..0000000 --- a/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)); -} |