esc to dismiss
x
Home / week-87 / 874

信息

题解

解法1: 利用栈模拟

pub fn backspace_compare(s: String, t: String) -> bool {
    fn sss(s: &str) -> Vec<u8> {
        let mut tmp = vec![];
        for b in s.as_bytes() {
            if *b == b'#' {
                tmp.pop();
            } else {
                tmp.push(*b);
            }
        }
        return tmp;
    }

    sss(s.as_str()).eq(&sss(t.as_str()))
}

时间复杂度 \(0(M+N)\) , 空间复杂度 \(O(M+N)\)

解法二: 双指针

# 只影响其前面的字符, 因此如果 从后向前 遍历, 对比两个相对位置的字符是否相同即可. 

pub fn backspace_compare(s: String, t: String) -> bool {
    let (s, t) = (s.as_bytes(), t.as_bytes());
    let (mut si, mut ti) = (s.len(), t.len()); // 留一个偏移, 防止usize溢出
    let (mut sd, mut td) = (0, 0);
    while si > 0 || ti > 0 {
        while si > 0 {
            if s[si - 1] == b'#' {
                // 回退符, 计数, 跳过
                sd += 1;
                si -= 1;
            } else if sd > 0 {
                // 需要回退, 回退一格
                sd -= 1;
                si -= 1;
            } else {
                break;
            }
        }
        while ti > 0 {
            if t[ti - 1] == b'#' {
                td += 1;
                ti -= 1;
            } else if td > 0 {
                td -= 1;
                ti -= 1;
            } else {
                break;
            }
        }

        if ti != 0 && si != 0 {
            // 同时没有到头, 判断一下
            if s[si - 1] != t[ti - 1] {
                return false;
            }
            // 相同, 两边同时向前一格
            si -= 1;
            ti -= 1;
        } else if ti != 0 || si != 0 {
            // 有一个还没有结束
            return false;
        }
    }
    true
}

Backlinks

Tags

x