2022-09-19：给定字符串 S and T，找出 S 中最短的（连续）子串 W ，使得 T 是 W

2022-09-19：给定字符串 S and T，找出 S 中最短的（连续）子串 W ，使得 T 是 W 的 子序列 。
如果 S 中没有窗口可以包含 T 中的所有字符，返回空字符串 “”。
如果有不止一个最短长度的窗口，返回开始位置最靠左的那个。
示例 1：
输入：
S = “abcdebdde”, T = “bde”
输出：”bcde”
解释：
“bcde” 是答案，因为它在相同长度的字符串 “bdde” 出现之前。
“deb” 不是一个更短的答案，因为在窗口中必须按顺序出现 T 中的元素。

答案2022-09-19：

动态规划。
时间复杂度：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
    }
}

执行结果如下：

左神java代码

本作品采用《CC 协议》，转载必须注明作者和本文链接