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 协议》,转载必须注明作者和本文链接
微信公众号:福大大架构师每日一题。最新面试题,涉及golang,rust,mysql,redis,云原生,算法,分布式,网络,操作系统。
讨论数量: 0
(= ̄ω ̄=)··· 暂无内容!

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容,与人为善,比聪明更重要!