844. Compare Strings with Backspace

LeetCode problem link (opens new window)

Given two strings S and T, return if they are equal when both are typed into empty text editors. # means a backspace character.

Note: If a backspace is encountered while the text is empty, the text remains empty.

Example 1:

• Input: S = "ab#c", T = "ad#c"
• Output: true
• Explanation: Both S and T become "ac".

Example 2:

• Input: S = "ab##", T = "c#d#"
• Output: true
• Explanation: Both S and T become "".

Example 3:

• Input: S = "a##c", T = "#a#c"
• Output: true
• Explanation: Both S and T become "c".

Example 4:

• Input: S = "a#c", T = "b"
• Output: false
• Explanation: S becomes "c", but T remains "b".

Approach

This article will discuss a stack simulation method with a space complexity of O(n) and a two-pointer method with a space complexity of O(1).

Basic Method (Using Stack)

This problem seems to be a perfect fit for stack usage. Such matching (elimination) problems are the strong suit of stacks. For those following along with the coding series, you might remember 1047.Remove All Adjacent Duplicates In String (opens new window) where we used a similar approach using stacks.

In this problem, even though a stack approach is feasible, using it creates unnecessary hassle during the comparison phase.

Instead of using a stack, let's use the string as a stack, utilizing its append and pop operations. When comparing the final results, comparing two strings is much easier than comparing stack elements.

The following code demonstrates this approach:

class Solution {
public:
    bool backspaceCompare(string S, string T) {
        string s;
        string t;
        for (int i = 0; i < S.size(); i++) {
            if (S[i] != '#') s += S[i];
            else if (!s.empty()) {
                s.pop_back();
            }
        }
        for (int i = 0; i < T.size(); i++) {
            if (T[i] != '#') t += T[i];
            else if (!t.empty()) {
                t.pop_back();
            }
        }
        return s == t;
    }
};

• Time Complexity: O(n + m), where n is the length of S and m is the length of T, or can be considered as O(n).
• Space Complexity: O(n + m)

To eliminate the repeated logic in the above code for processing S and T, we can refactor it as follows:

class Solution {
private:
    string getString(const string& S) {
        string s;
        for (int i = 0; i < S.size(); i++) {
            if (S[i] != '#') s += S[i];
            else if (!s.empty()) {
                s.pop_back();
            }
        }
        return s;
    }
public:
    bool backspaceCompare(string S, string T) {
        return getString(S) == getString(T);
    }
};

The performance remains:

• Time Complexity: O(n + m)
• Space Complexity: O(n + m)

Optimized Method (Two Pointers From End)

We can also solve this problem with space complexity of O(1).

Traverse S and T simultaneously from the back (initializing i to end of S and j to end of T), keeping track of the number of # characters encountered, and simulating the backspace operation. If the backspace count is zero, start comparing S[i] to T[j].

The animation is as follows:

If S[i] and T[j] are not the same, return false. If one pointer (i or j) reaches the start of the string first, also return false.

Here is the implementation:

class Solution {
public:
    bool backspaceCompare(string S, string T) {
        int sSkipNum = 0;
        int tSkipNum = 0;
        int i = S.size() - 1;
        int j = T.size() - 1;
        while (true) {
            while (i >= 0) {
                if (S[i] == '#') sSkipNum++;
                else {
                    if (sSkipNum > 0) sSkipNum--;
                    else break;
                }
                i--;
            }
            while (j >= 0) {
                if (T[j] == '#') tSkipNum++;
                else {
                    if (tSkipNum > 0) tSkipNum--;
                    else break;
                }
                j--;
            }
            if (i < 0 || j < 0) break;
            if (S[i] != T[j]) return false;
            i--; j--;
        }
        return i == -1 && j == -1;
    }
};

• Time Complexity: O(n + m)
• Space Complexity: O(1)

Implementations in Other Languages

Java

// Basic Method (Using Stack)
class Solution {
    public boolean backspaceCompare(String s, String t) {
        StringBuilder ssb = new StringBuilder();
        StringBuilder tsb = new StringBuilder();
        for (char c : s.toCharArray()) {
            if (c != '#') {
                ssb.append(c);
            } else if (ssb.length() > 0) {
                ssb.deleteCharAt(ssb.length() - 1);
            }
        }
        for (char c : t.toCharArray()) {
            if (c != '#') {
                tsb.append(c);
            } else if (tsb.length() > 0) {
                tsb.deleteCharAt(tsb.length() - 1);
            }
        }
        return ssb.toString().equals(tsb.toString());
    }
}

Two Pointers:

class Solution {
    public static boolean backspaceCompare(String s, String t) {
        char[] sarray = s.toCharArray();
        char[] tarray = t.toCharArray();
        return generate(sarray).equals(generate(tarray));
    }
    public static String generate(char[] a) {
        int slow = -1;
        int fast = 0;
        if (a.length == 1) {
            return new String(a);
        } else {
            for (fast = 0; fast < a.length; fast++) {
                if (a[fast] != '#')
                    a[++slow] = a[fast];
                else{
                    if (slow >= 0)
                        slow--;
                }
            }
            return new String(a, 0, slow + 1);
        }
    }
}

class Solution {
    public static boolean backspaceCompare(String s, String t) {
        return getStr(s).equals(getStr(t));
    }

    public static String getStr(String s) {
        int slowIndex;
        int fastIndex = 0;
        StringBuilder builder = new StringBuilder(s);
        for (slowIndex = 0; fastIndex < s.length(); fastIndex++) {
            if (builder.charAt(fastIndex) != '#') {
                builder.setCharAt(slowIndex++, builder.charAt(fastIndex));
            } else {
                if (slowIndex > 0) {
                    slowIndex--;
                }
            }
        }
        return builder.toString().substring(0, slowIndex);
    }
}

From End Two-Pointers:

class Solution {
    public static boolean backspaceCompare(String s, String t) {
        int sSkipNum = 0;
        int tSkipNum = 0;
        int sIndex = s.length() - 1;
        int tIndex = t.length() - 1;
        while (true) {
            while (sIndex >= 0) {
                if (s.charAt(sIndex) == '#') {
                    sSkipNum++;
                } else {
                    if (sSkipNum > 0) {
                        sSkipNum--;
                    } else {
                        break;
                    }
                }
                sIndex--;
            }
            while (tIndex >= 0) {
                if (t.charAt(tIndex) == '#') {
                    tSkipNum++;
                } else {
                    if (tSkipNum > 0) {
                        tSkipNum--;
                    } else {
                        break;
                    }
                }
                tIndex--;
            }
            if (sIndex < 0 || tIndex < 0) {
                break;
            }
            if (s.charAt(sIndex) != t.charAt(tIndex)) {
                return false;
            }
            sIndex--;
            tIndex--;
        }
        return sIndex == -1 && tIndex == -1;
    }
}

Python

class Solution:

    def get_string(self, s: str) -> str:
        bz = []
        for i in range(len(s)):
            c = s[i]
            if c != '#':
                bz.append(c)
            elif len(bz) > 0:
                bz.pop()
        return str(bz)

    def backspaceCompare(self, s: str, t: str) -> bool:
        return self.get_string(s) == self.get_string(t)
        pass

Two Pointers:

class Solution:
    def backspaceCompare(self, s: str, t: str) -> bool:
        s_index, t_index = len(s) - 1, len(t) - 1
        s_backspace, t_backspace = 0, 0
        while s_index >= 0 or t_index >= 0:
            while s_index >= 0: 
                if s[s_index] == '#':
                    s_index -= 1
                    s_backspace += 1
                else:
                    if s_backspace > 0:
                        s_index -= 1
                        s_backspace -= 1
                    else:
                        break
            while t_index >= 0: 
                if t[t_index] == '#':
                    t_index -= 1
                    t_backspace += 1
                else:
                    if t_backspace > 0:
                        t_index -= 1
                        t_backspace -= 1
                    else:
                        break
            if s_index >= 0 and t_index >= 0:
                if s[s_index] != t[t_index]:
                    return False
            elif s_index >= 0 or t_index >= 0:
                return False
            s_index -= 1
            t_index -= 1
        return True

Go

func getString(s string) string {
    bz := []rune{}
    for _, c := range s {
        if c != '#' {
            bz = append(bz, c)
        } else if len(bz) > 0 {
            bz = bz[:len(bz)-1]
        }
    }
    return string(bz)
}

func backspaceCompare(s string, t string) bool {
    return getString(s) == getString(t)
}

Two Pointers:

func backspaceCompare(s string, t string) bool {
    s_index, t_index := len(s) - 1, len(t) - 1
    s_backspace, t_backspace := 0, 0
    for s_index >= 0 || t_index >= 0 {
        for s_index >= 0 {
            if s[s_index] == '#' {
                s_index--
                s_backspace++
            } else {
                if s_backspace > 0 {
                    s_index--
                    s_backspace--
                } else {
                    break
                }
            }            
        }
        for t_index >= 0 {
            if t[t_index] == '#' {
                t_index--
                t_backspace++
            } else {
                if t_backspace > 0 {
                    t_index--
                    t_backspace--
                } else {
                    break
                }
            }
        }
        if s_index >= 0 && t_index >= 0 {
            if s[s_index] != t[t_index] {
                return false
            } 
        } else if s_index >= 0 || t_index >= 0 {
            return false
        }            
        s_index--
        t_index--
    }      
    return true
}

JavaScript

// Double Stack
var backspaceCompare = function(s, t) {
    const arrS = [], arrT = [];
    for (let char of s) {
        char === '#' ? arrS.pop() : arrS.push(char);
    }
    for (let char of t) {
        char === '#' ? arrT.pop() : arrT.push(char);
    }
    return arrS.join('') === arrT.join('');
};

// Simplified
var backspaceCompare = function(s, t) {
    const getString = s => {
        let arrS = [];
        for (let char of s) {
            char === '#' ? arrS.pop() : arrS.push(char);
        }
        return arrS.join('');
    }
    return getString(s) === getString(t);
};

// Two Pointers
var backspaceCompare = function(s, t) {
    let sSkipNum = 0;
    let tSkipNum = 0;
    let i = s.length - 1, j = t.length - 1;
    while(true) {
        while(i >= 0){
            if(s[i] === '#') sSkipNum++;
            else {
                if (sSkipNum > 0) sSkipNum--;
                else break;
            }
            i--;
        }
        while (j >= 0) {
            if (t[j] === '#') tSkipNum++;
            else {
                if (tSkipNum > 0) tSkipNum--;
                else break;
            }
            j--;
        }
        if (i < 0 || j < 0) break;
        if (s[i] !== t[j]) return false;
        i--; j--;
    }
    if (i == -1 && j == -1) return true;
    return false;
};

TypeScript

Double Stack Method:

function backspaceCompare(s: string, t: string): boolean {
    const stack1: string[] = [],
        stack2: string[] = [];
    for (let c of s) {
        if (c === '#') {
            stack1.pop();
        } else {
            stack1.push(c);
        }
    }
    for (let c of t) {
        if (c === '#') {
            stack2.pop();
        } else {
            stack2.push(c);
        }
    }
    if (stack1.length !== stack2.length) return false;
    for (let i = 0, length = stack1.length; i < length; i++) {
        if (stack1[i] !== stack2[i]) return false;
    }
    return true;
};

Two Pointers Method:

function backspaceCompare(s: string, t: string): boolean {
    let sIndex: number = s.length - 1,
        tIndex: number = t.length - 1;
    while (true) {
        sIndex = getIndexAfterDel(s, sIndex);
        tIndex = getIndexAfterDel(t, tIndex);
        if (sIndex < 0 || tIndex < 0) break;
        if (s[sIndex] !== t[tIndex]) return false;
        sIndex--;
        tIndex--;
    }
    return sIndex === -1 && tIndex === -1;
};
function getIndexAfterDel(s: string, startIndex: number): number {
    let backspaceNum: number = 0;
    while (startIndex >= 0) {
        if (s[startIndex] !== '#' && backspaceNum === 0) break;
        if (s[startIndex] === '#') {
            backspaceNum++;
        } else {
            backspaceNum--;
        }
        startIndex--;
    }
    return startIndex;
}

Rust

Two Pointers

impl Solution {
    pub fn backspace_compare(s: String, t: String) -> bool {
        let (s, t) = (
            s.chars().collect::<Vec<char>>(),
            t.chars().collect::<Vec<char>>(),
        );
        Self::get_string(s) == Self::get_string(t)
    }

    pub fn get_string(mut chars: Vec<char>) -> Vec<char> {
        let mut slow = 0;
        for i in 0..chars.len() {
            if chars[i] == '#' {
                slow = (slow as u32).saturating_sub(1) as usize;
            } else {
                chars[slow] = chars[i];
                slow += 1;
            }
        }
        chars.truncate(slow);
        chars
    }
}

Double Stack Method

impl Solution {
    pub fn backspace_compare(s: String, t: String) -> bool {
        Self::get_string(s) == Self::get_string(t)
    }

    pub fn get_string(string: String) -> String {
        let mut s = String::new();
        for c in string.chars() {
            if c != '#' {
                s.push(c);
            } else if !s.is_empty() {
                s.pop();
            }
        }
        s
    }
}