|
| 1 | +/** |
| 2 | + * [132] Palindrome Partitioning II |
| 3 | + * |
| 4 | + * Given a string s, partition s such that every substring of the partition is a palindrome. |
| 5 | + * |
| 6 | + * Return the minimum cuts needed for a palindrome partitioning of s. |
| 7 | + * |
| 8 | + * Example: |
| 9 | + * |
| 10 | + * |
| 11 | + * Input: "aab" |
| 12 | + * Output: 1 |
| 13 | + * Explanation: The palindrome partitioning ["aa","b"] could be produced using 1 cut. |
| 14 | + * |
| 15 | + * |
| 16 | + */ |
| 17 | +pub struct Solution {} |
| 18 | + |
| 19 | +// submission codes start here |
| 20 | + |
| 21 | +/* |
| 22 | + 为了方便讨论, 我们记 n 个字符的最少回文分段是 f(n), 则切分次数为 f(n)-1, 接下来递推 f(n): |
| 23 | +
|
| 24 | + f(n) = min(f(n-i) + 1) { i in [0..n] and s[i..n] is palindrome } |
| 25 | +
|
| 26 | + 显然, f(1) 为 1, f(0) 为 0 |
| 27 | +
|
| 28 | + 判断 is_palindrome 也需要优化, 使用一个备忘录, 将判断回文的操作优化到 O(1): |
| 29 | +
|
| 30 | + is_palindrome(s[i..n]) = s[i] == s[n] && is_palindrome(s[i+1..n-1]) |
| 31 | +
|
| 32 | + 最后的复杂度: 时间 O(N^2), 空间 O(N^2) |
| 33 | + */ |
| 34 | +impl Solution { |
| 35 | + pub fn min_cut(s: String) -> i32 { |
| 36 | + let s = s.chars().collect::<Vec<_>>(); |
| 37 | + if s.is_empty() { return 0 } |
| 38 | + let mut palindrome_cache: Vec<Vec<Option<bool>>> = vec![vec![None; s.len()]; s.len()]; |
| 39 | + let mut min = Vec::with_capacity(s.len()+1); |
| 40 | + min.push(0); |
| 41 | + min.push(1); |
| 42 | + for i in 1..s.len() { |
| 43 | + let mut local_min = i32::max_value(); |
| 44 | + for j in 0..i+1 { |
| 45 | + if Solution::is_palindrome(&mut palindrome_cache, &s, j, i) { |
| 46 | + local_min = i32::min(1 + min[j], local_min); |
| 47 | + } |
| 48 | + } |
| 49 | + min.push(local_min); |
| 50 | + } |
| 51 | + min[s.len()] - 1 |
| 52 | + } |
| 53 | + |
| 54 | + fn is_palindrome(cache: &mut Vec<Vec<Option<bool>>>, s: &Vec<char>, i: usize, j: usize) -> bool { |
| 55 | + if j <= i { return true } |
| 56 | + if let Some(result) = cache[i][j] { |
| 57 | + result |
| 58 | + } else { |
| 59 | + let result = s[i] == s[j] && (i + 1 > s.len() || j < 1 || Solution::is_palindrome(cache, s, i+1, j-1)); |
| 60 | + cache[i][j] = Some(result); |
| 61 | + result |
| 62 | + } |
| 63 | + } |
| 64 | +} |
| 65 | + |
| 66 | +// submission codes end |
| 67 | + |
| 68 | +#[cfg(test)] |
| 69 | +mod tests { |
| 70 | + use super::*; |
| 71 | + |
| 72 | + #[test] |
| 73 | + fn test_132() { |
| 74 | + assert_eq!(Solution::min_cut("aab".to_owned()), 1); |
| 75 | + assert_eq!(Solution::min_cut("aaa".to_owned()), 0); |
| 76 | + assert_eq!(Solution::min_cut("aabb".to_owned()), 1); |
| 77 | + } |
| 78 | +} |
0 commit comments