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 <= S.length <= 2001 <= T.length <= 200SandTonly contain lowercase letters and'#'characters.
Follow up:
- Can you solve it in
O(N)time andO(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 } }