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 <= 200
1 <= T.length <= 200
S
andT
only 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 } }