844. Compare strings containing backspace

The title

Given two strings S and T, when each is entered into a blank text editor, determine if the two are equal and return the result. # stands for backspace character. Note: If you enter a backspace character for empty text, the text remains empty. Example 1:

Enter: S ="ab#c", T = "ad#c"Output:trueExplanation: both S and T become "ac". Enter: S ="a##c", T = "#a#c"Output:trueExplanation: both S and T become "C". Enter: S ="a#c", T = "b"Output:falseExplanation: S becomes a "C", but T is still a "B".Copy the code

Train of thought

Double stack method, reconstruct string

/** * @param {string} S * @param {string} T * @return {boolean} */
var backspaceCompare = function(S, T) {
    if(! S && ! T) {return true }
    const buildStr = function(str) {
        const stack = []
        let copyStr = ' '
        for (let i = 0; i < str.length; i++) {
            const temp = str[i]
            if (temp === The '#') {
                stack.pop()
            } else {
                stack.push(temp)
            }
        }
        while(stack.length) {
            copyStr += stack.pop()
        }
        return copyStr
    }
    return buildStr(S) === buildStr(T)
};
Copy the code

Time complexity O(m+n). Space complexity order m+n.

Double pointer

/** * @param {string} S * @param {string} T * @return {boolean} */
var backspaceCompare = function(S, T) {
    if(! S && ! T) {return true }
    let i = S.length - 1 // index of S
    let j = T.length - 1 // Index of T
    let skipSCount = 0 // S counter for #
    let skipTCount = 0 // T counter for #
    // go through S and T from back to front
    while(i >= 0 || j >= 0) {
        If # is encountered, the character to the left should be deleted
        // If no # is encountered at the same time when the counter >0, then the counter -1, index -1, otherwise out of the loop processing
        while(i >= 0) {
            if (S[i] === The '#') {
                skipSCount++
                i--
            } else if (skipSCount > 0) {
                skipSCount--
                i--
            } else {
                break}}while(j >= 0) {
            if (T[j] === The '#') {
                skipTCount++
                j--
            } else if (skipTCount > 0) {
                skipTCount--
                j--
            } else {
                break}}// If the two characters are not equal, it is not equal
        if (i >= 0 && j >= 0&& S[i] ! == T[j]) {return false
        }
        // If either index is negative, the index is not equal
        if (i >= 0! == j >=0) {
            return false
        }
        i--;
        j--;
    }
    return true
};
Copy the code

Time complexity O(m+n). Space complexity O(1).

advertising

If you think it’s interesting, click on the lower right corner, or pay attention to it directly.