Given a non-empty string, encode the string such that its encoded length is the shortest.
The encoding rule is: k[encoded_string]
, where the encoded_string
inside the square brackets is being repeated exactly k
times.
Note:
k
will be a positive integer.
Example 1:
Input: s = "aaa" Output: "aaa" Explanation: There is no way to encode it such that it is shorter than the input string, so we do not encode it.
Example 2:
Input: s = "aaaaa" Output: "5[a]" Explanation: "5[a]" is shorter than "aaaaa" by 1 character.
Example 3:
Input: s = "aaaaaaaaaa" Output: "10[a]" Explanation: "a9[a]" or "9[a]a" are also valid solutions, both of them have the same length = 5, which is the same as "10[a]".
Example 4:
Input: s = "aabcaabcd" Output: "2[aabc]d" Explanation: "aabc" occurs twice, so one answer can be "2[aabc]d".
Example 5:
Input: s = "abbbabbbcabbbabbbc" Output: "2[2[abbb]c]" Explanation: "abbbabbbc" occurs twice, but "abbbabbbc" can also be encoded to "2[abbb]c", so one answer can be "2[2[abbb]c]".
Constraints:
1 <= s.length <= 150
s
consists of only lowercase English letters.struct Solution;
use std::collections::HashMap;
impl Solution {
fn encode(s: String) -> String {
let mut memo: HashMap<String, String> = HashMap::new();
Self::dp(s, &mut memo)
}
fn dp(s: String, memo: &mut HashMap<String, String>) -> String {
if let Some(res) = memo.get(&s) {
return res.to_string();
}
let n = s.len();
let mut res = s.to_string();
for i in 1..n {
if n % i == 0 {
let k = n / i;
if (0..k).all(|j| s[0..i] == s[j * i..(j + 1) * i]) {
let t = format!("{}[{}]", k, Self::dp(s[0..i].to_string(), memo));
if t.len() < res.len() {
res = t;
}
}
}
}
for i in 1..n {
let t = format!(
"{}{}",
Self::dp(s[0..i].to_string(), memo),
Self::dp(s[i..].to_string(), memo)
);
if t.len() < res.len() {
res = t;
}
}
memo.insert(s, res.to_string());
res
}
}
#[test]
fn test() {
let s = "aaa".to_string();
let res = "aaa".to_string();
assert_eq!(Solution::encode(s), res);
let s = "aaaaa".to_string();
let res = "5[a]".to_string();
assert_eq!(Solution::encode(s), res);
let s = "aabcaabcd".to_string();
let res = "2[aabc]d".to_string();
assert_eq!(Solution::encode(s), res);
let s = "abbbabbbcabbbabbbc".to_string();
let res = "2[2[abbb]c]".to_string();
assert_eq!(Solution::encode(s), res);
}