政务网站建设交流发言,wordpress 宠物模板,网站建设方面书籍,网站建设珠海 新盈科技公司2023-03-31#xff1a;给定一个字符串 s#xff0c;返回 s 中不同的非空 回文子序列 个数#xff0c; 通过从 s 中删除 0 个或多个字符来获得子序列。 如果一个字符序列与它反转后的字符序列一致#xff0c;那么它是 回文字符序列。 如果有某个 i , 满足 ai ! bi #xff…2023-03-31给定一个字符串 s返回 s 中不同的非空 回文子序列 个数 通过从 s 中删除 0 个或多个字符来获得子序列。 如果一个字符序列与它反转后的字符序列一致那么它是 回文字符序列。 如果有某个 i , 满足 ai ! bi 则两个序列 a1, a2, … 和 b1, b2, … 不同。 注意结果可能很大你需要对 10^9 7 取模。
答案2023-03-31
题目要求计算一个给定字符串中不同的非空回文子序列个数并对结果取模。我们可以使用动态规划来解决这个问题。
首先定义一个二维数组dp其中dp[i][j]表示从第i个字符到第j个字符中所有可能的回文子序列数量。
对于每个i和j如果s[i]s[j]则有三种情况
1.空字符串或两个字符本身如aa 2.单个字符或两个字符本身如a或aaa 3.包含左右两个字符的回文子序列同时需要减去内部相同字符的回文子序列数量。 因此我们可以将dp[i][j]初始化为0并按照以下公式更新
dp[i][j] dp[i1][j-1] * 2 - dp[l1][r-1] 2 或 dp[i1][j-1] * 2 1 或 dp[i1][j-1] * 2 - dp[l1][r-1]
其中l和r分别表示字符串中从第i个字符到第j个字符之间的一个相同字符的最左侧位置和最右侧位置。例如在字符串bccb中当i0且j3时l1r2。
如果s[i]!s[j]则有两种情况
1.包含右边字符的回文子序列数量 2.包含左边字符的回文子序列数量。 同时需要注意重复计算的空回文子序列数量。因此我们可以将dp[i][j]初始化为0并按照以下公式更新
dp[i][j] dp[i][j-1] dp[i1][j] - dp[i1][j-1]
最后我们可以使用哈希表来存储每个位置左侧和右侧相同字符的最后出现位置这样可以将空间复杂度降至O(n)。在进行模运算时直接对所有中间结果进行取模可能会导致整数溢出因此可以在计算过程中每一步都进行取模操作也可以使用Rust中提供的取模运算符%。
时间复杂度
1.预处理左侧和右侧相同字符最后出现位置的时间复杂度为O(n)。 2.动态规划的过程中需要计算长度从2到n的所有可能情况因此时间复杂度为O(n^2)。 3.因此总时间复杂度为O(n^2)。
空间复杂度
1.需要使用一个二维数组dp存储回文子序列数量因此空间复杂度为O(n^2)。 2.此外还需要使用两个一维数组left和right分别存储每个位置左侧和右侧相同字符的最后出现位置因此空间复杂度为O(n)。 3.因此总空间复杂度为O(n^2)。
rust代码如下
use std::collections::HashMap;fn count_palindromic_subsequences(s: str) - i32 {let mod_value 1000000007;let s_chars: Vecchar s.chars().collect(); // 将字符串转成字符数组let n s_chars.len() as i32; // 计算字符数组长度let mut right vec![0; n as usize]; // 存储每个位置右侧相同字符的最后出现位置let mut left vec![0; n as usize]; // 存储每个位置左侧相同字符的最后出现位置let mut last HashMap::new();for i in 0..n {left[i as usize] *last.get(s_chars[i as usize]).unwrap_or((-1)); // 获取当前字符左侧相同字符的最后位置last.insert(s_chars[i as usize], i); // 更新当前字符的最后出现位置}last.clear();for i in (0..n).rev() {right[i as usize] *last.get(s_chars[i as usize]).unwrap_or(n); // 获取当前字符右侧相同字符的最后位置last.insert(s_chars[i as usize], i); // 更新当前字符的最后出现位置}let mut dp vec![vec![0i64; n as usize]; n as usize]; // 存储回文子序列数量的二维数组for i in 0..n {dp[i as usize][i as usize] 1; // 单个字符为回文子序列}for i in (0..n - 1).rev() {for j in i 1..n {if s_chars[i as usize] s_chars[j as usize] {// 如果左右两个字符相同let l std::cmp::min(j, right[i as usize]); // 计算内部回文子序列的左边界let r std::cmp::max(i, left[j as usize]); // 计算内部回文子序列的右边界if l r {// 内部没有相同字符dp[i as usize][j as usize] dp[i as usize 1][j as usize - 1] * 2 2;// 新增的两个字符以及空字符串和两个字符本身两种情况} else if l r {// 内部只有一个相同字符dp[i as usize][j as usize] dp[i as usize 1][j as usize - 1] * 2 1;// 新增的两个字符以及单个字符和两个字符本身三种情况} else {// 内部有两个或以上相同字符dp[i as usize][j as usize] dp[i as usize 1][j as usize - 1] * 2 // 包含左右字符的回文子序列数量- dp[(l 1) as usize][(r - 1) as usize] // 减去内部相同字符的回文子序列数量 mod_value; // 模运算}} else {// 如果左右两个字符不同dp[i as usize][j as usize] dp[i as usize][j as usize - 1] // 包含右边字符的回文子序列数量 dp[i as usize 1][j as usize] // 包含左边字符的回文子序列数量- dp[i as usize 1][j as usize - 1] // 重复计算的空回文子序列数量 mod_value; // 模运算}dp[i as usize][j as usize] % mod_value; // 模运算}}dp[0][n as usize - 1] as i32 // 返回包含所有字符的回文子序列数量
}fn main() {let s abcdabcdabcdabcdabcdabcdabcdabcddcbadcbadcbadcbadcbadcbadcbadcba;println!({}, count_palindromic_subsequences(s));
}
