给定字符串 S and T，找出 S 中最短的（连续）子串 W ，使得 T 是 W 的 子序列 。
如果 S 中没有窗口可以包含 T 中的所有字符，返回空字符串 “”。
如果有不止一个最短长度的窗口，返回开始位置最靠左的那个。
示例 1：
输入：
S = “abcdebdde”, T = “bde”
输出：“bcde”
解释：
“bcde” 是答案，因为它在相同长度的字符串 “bdde” 出现之前。
“deb” 不是一个更短的答案，因为在窗口中必须按顺序出现 T 中的元素。
动态规划。
时间复杂度：O(NM)。
空间复杂度：O(NM)。
代码用rust编写。代码如下：
fn main() {
let s = "xxaxxbxxcxxaxbyc";
let t = "abc";
let ans = min_window4(s, t);
println!("ans = {}", ans);
}
const MAX_VALUE: i32 = 1 << 31 - 1;
fn min_window4(s: &str, t: &str) -> String {
let str = s.as_bytes();
let target = t.as_bytes();
let n = str.len() as i32;
let m = target.len() as i32;
let mut dp: Vec<Vec<i32>> = vec![];
for i in 0..n + 1 {
dp.push(vec![]);
for _ in 0..m + 1 {
dp[i as usize].push(0);
}
}
for si in 0..=n {
dp[si as usize][m as usize] = si;
}
for ti in 0..m {
dp[n as usize][ti as usize] = MAX_VALUE;
}
let mut si = n - 1;
while si >= 0 {
let mut ti = m - 1;
while ti >= 0 {
let r1 = dp[(si + 1) as usize][ti as usize];
let r2 = if str[si as usize] == target[ti as usize] {
dp[(si + 1) as usize][(ti + 1) as usize]
} else {
MAX_VALUE
};
dp[si as usize][ti as usize] = get_min(r1, r2);
ti -= 1;
}
si -= 1;
}
let mut len = MAX_VALUE;
let mut l = -1;
let mut r = -1;
for si in 0..str.len() as i32 {
let right = dp[si as usize][0];
if right != MAX_VALUE && right - si < len {
len = dp[si as usize][0] - si;
l = si;
r = right;
}
}
return if l == -1 {
String::from("")
} else {
String::from(&s[l as usize..r as usize])
};
}
fn get_min<T: Clone + Copy + std::cmp::PartialOrd>(a: T, b: T) -> T {
if a < b {
a
} else {
b
}
}执行结果如下：
