Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/844.html

844. Backspace String Compare (Easy)

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

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" while T becomes "b".

Note:

  1. 1 <= S.length <= 200
  2. 1 <= T.length <= 200
  3. S and T only contain lowercase letters and '#' characters.

Follow up:

  • Can you solve it in O(N) time and O(1) space?

Solution 1.

Update the S and T to the results of applying backspaces, then compare the strings.

// OJ: https://leetcode.com/problems/backspace-string-compare/
// Time: O(N)
// Space: O(1)
class Solution {
    string normalize(string &s) {
        int len = 0;
        for (char c : s) {
            if (c == '#') len = max(len - 1, 0);
            else s[len++] = c;
        }
        s.resize(len);
        return s;
    }
public:
    bool backspaceCompare(string S, string T) {
        return normalize(S) == normalize(T);
    }
};

Solution 2.

If it’s not allowed to change the input string, we scan backward. back function is used to skip all characters that are deleted using backspaces. After back, the indexes are pointing to characters that we need to compare.

// OJ: https://leetcode.com/problems/backspace-string-compare/
// Time: O(N)
// Space: O(1)
class Solution {
    void back(string &s, int &i) {
        if (i < 0 || s[i] != '#') return;
        int cnt = 0;
        for (; i >= 0 && (cnt || s[i] == '#'); --i) {
            if (s[i] == '#') ++cnt;
            else --cnt;
        }
    }
public:
    bool backspaceCompare(string S, string T) {
        int i = S.size() - 1, j = T.size() - 1;
        while (i >= 0 || j >= 0) {
            back(S, i);
            back(T, j);
            if ((i >= 0 && j < 0) || (i < 0 && j >= 0)) return false;
            for (; i >= 0 && j >= 0 && S[i] != '#' && T[j] != '#'; --i, --j) {
                if (S[i] != T[j]) return false;
            } 
        }
        return true;
    }
};
  • class Solution {
        public boolean backspaceCompare(String S, String T) {
            StringBuffer sb1 = new StringBuffer();
            StringBuffer sb2 = new StringBuffer();
            int length1 = S.length(), length2 = T.length();
            for (int i = 0; i < length1; i++) {
                char c = S.charAt(i);
                if (c == '#') {
                    if (sb1.length() > 0)
                        sb1.deleteCharAt(sb1.length() - 1);
                } else
                    sb1.append(c);
            }
            for (int i = 0; i < length2; i++) {
                char c = T.charAt(i);
                if (c == '#') {
                    if (sb2.length() > 0)
                        sb2.deleteCharAt(sb2.length() - 1);
                } else
                    sb2.append(c);
            }
            return sb1.toString().equals(sb2.toString());
        }
    }
    
    ############
    
    class Solution {
        public boolean backspaceCompare(String s, String t) {
            int i = s.length() - 1, j = t.length() - 1;
            int skip1 = 0, skip2 = 0;
            for (; i >= 0 || j >= 0; --i, --j) {
                while (i >= 0) {
                    if (s.charAt(i) == '#') {
                        ++skip1;
                        --i;
                    } else if (skip1 > 0) {
                        --skip1;
                        --i;
                    } else {
                        break;
                    }
                }
                while (j >= 0) {
                    if (t.charAt(j) == '#') {
                        ++skip2;
                        --j;
                    } else if (skip2 > 0) {
                        --skip2;
                        --j;
                    } else {
                        break;
                    }
                }
                if (i >= 0 && j >= 0) {
                    if (s.charAt(i) != t.charAt(j)) {
                        return false;
                    }
                } else if (i >= 0 || j >= 0) {
                    return false;
                }
            }
            return true;
        }
    }
    
  • // OJ: https://leetcode.com/problems/backspace-string-compare/
    // Time: O(N)
    // Space: O(1)
    class Solution {
        string normalize(string &s) {
            int len = 0;
            for (char c : s) {
                if (c == '#') len = max(len - 1, 0);
                else s[len++] = c;
            }
            s.resize(len);
            return s;
        }
    public:
        bool backspaceCompare(string S, string T) {
            return normalize(S) == normalize(T);
        }
    };
    
  • class Solution:
        def backspaceCompare(self, s: str, t: str) -> bool:
            i, j, skip1, skip2 = len(s) - 1, len(t) - 1, 0, 0
            while i >= 0 or j >= 0:
                while i >= 0:
                    if s[i] == '#':
                        skip1 += 1
                        i -= 1
                    elif skip1:
                        skip1 -= 1
                        i -= 1
                    else:
                        break
                while j >= 0:
                    if t[j] == '#':
                        skip2 += 1
                        j -= 1
                    elif skip2:
                        skip2 -= 1
                        j -= 1
                    else:
                        break
                if i >= 0 and j >= 0:
                    if s[i] != t[j]:
                        return False
                elif i >= 0 or j >= 0:
                    return False
                i, j = i - 1, j - 1
            return True
    
    ############
    
    if s == '#':
        if ans_S:
            ans_S = ans_S[:-1]
    
  • func backspaceCompare(s string, t string) bool {
    	i, j := len(s)-1, len(t)-1
    	skip1, skip2 := 0, 0
    	for ; i >= 0 || j >= 0; i, j = i-1, j-1 {
    		for i >= 0 {
    			if s[i] == '#' {
    				skip1++
    				i--
    			} else if skip1 > 0 {
    				skip1--
    				i--
    			} else {
    				break
    			}
    		}
    		for j >= 0 {
    			if t[j] == '#' {
    				skip2++
    				j--
    			} else if skip2 > 0 {
    				skip2--
    				j--
    			} else {
    				break
    			}
    		}
    		if i >= 0 && j >= 0 {
    			if s[i] != t[j] {
    				return false
    			}
    		} else if i >= 0 || j >= 0 {
    			return false
    		}
    	}
    	return true
    }
    
  • function backspaceCompare(s: string, t: string): boolean {
        let i = s.length - 1;
        let j = t.length - 1;
        while (i >= 0 || j >= 0) {
            let skip = 0;
            while (i >= 0) {
                if (s[i] === '#') {
                    skip++;
                } else if (skip !== 0) {
                    skip--;
                } else {
                    break;
                }
                i--;
            }
            skip = 0;
            while (j >= 0) {
                if (t[j] === '#') {
                    skip++;
                } else if (skip !== 0) {
                    skip--;
                } else {
                    break;
                }
                j--;
            }
            if (s[i] !== t[j]) {
                return false;
            }
            i--;
            j--;
        }
        return true;
    }
    
    
  • impl Solution {
        pub fn backspace_compare(s: String, t: String) -> bool {
            let (s, t) = (s.as_bytes(), t.as_bytes());
            let (mut i, mut j) = (s.len(), t.len());
            while i != 0 || j != 0 {
                let mut skip = 0;
                while i != 0 {
                    if s[i - 1] == b'#' {
                        skip += 1;
                    } else if skip != 0 {
                        skip -= 1;
                    } else {
                        break;
                    }
                    i -= 1
                }
                skip = 0;
                while j != 0 {
                    if t[j - 1] == b'#' {
                        skip += 1;
                    } else if skip != 0 {
                        skip -= 1;
                    } else {
                        break;
                    }
                    j -= 1
                }
                if i == 0 && j == 0 {
                    break;
                }
                if i == 0 || j == 0 {
                    return false;
                }
                if s[i - 1] != t[j - 1] {
                    return false;
                }
                i -= 1;
                j -= 1;
            }
            true
        }
    }
    
    

All Problems

All Solutions