Given two strings s and t, return true if they are equal when both are typed into empty text editors. '#' means a backspace character.
Note that after backspacing an empty text, the text will continue empty.
bakspae delete previous har
two string equal ontain same har
ab=abgghh
a=ab
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 = "b"
Output: false
Explanation: s becomes "c" while t becomes "b".
Verify constraints
What happens two # appear beside each other ? delete the two values before the first #
"ab##" ==> ""
What happens to # when there is no character to remove? it deletes nothing then, just like backspace would
"a###b"
after first # there is no char to delete
Are two empty string equal to each other
S:"x#y#z" T:"a#" ==>""
both S and T give same result
Does the case sensitivity matter?
yes it does,"a" does not equal "A"
cases
S:"ab#z" t:"az#z" true
S:"abc#d" t:"acc#c" false
S:"x#y#z#" t:"a#" true
S:"a###b" t:"b" true
S:"Ab#z" t:"ab#z" false
S:"Az" t:"az" false
S:"[a,z]" t:"[a,z]" true
coding out through brute force solution
const builtString= function(string)
{
const builtArray=[];
for(let p=0;p<string.length;p++)
{
if(string[p]!=='#')
{
builtArray.push(string[p]);
}
else{
builtArray.pop();
}
}
return builtArray;
}
Explanation
eg: ab#d#e
string.length=6
if(string[p]!=='#')
{
builtArray.push(string[p]);
}
so {a} by builtArray.push(string[p]);
next loop p=1
if(string[p]!=='#')
{
builtArray.push(string[p]);
}
so {a,b} builtArray.push(string[p]);
next loop p=2
else{
builtArray.pop();
}
so so {a} builtArray.pop();
next loop p=3
if(string[p]!=='#')
{
builtArray.push(string[p]);
}
so so {a,d} builtArray.push(string[p]);
next loop p=4
else{
builtArray.pop();
}
so so {a} builtArray.pop();
next loop p=5
if(string[p]!=='#')
{
builtArray.push(string[p]);
}
so so {a,e} builtArray.push(string[p]);
const backspace compare== function(S,T){
const final s=buildString(s); // call above coding
const final T=buildString(T);
if(finals.length!==final(T.length)
{
return false;
}
else{
for(let p=0:p<final.length:++)
{
if(final s[p]!==finalt[p])
{
return false;
}
}
}
return true;
}
Explanation
s:ag#b T:af#b
const final s=buildString(s)= s:ag#b
onst final T=buildString(T)=af#b
if(final(s.length)!==final(T.length))
{
return false;
}
s:ab length 2 T: asdf length 4
final(s.length)= final(T.length) ==>2!==4 return false
class Solution {
public boolean backspaceCompare(String s, String t) {
int i = s.length() -1;
int j = t.length() -1;
while(i>= 0 || j >= 0){
if((i >= 0 && s.charAt(i) == '#') || (j >= 0 && t.charAt(j) == '#'))
{
if(i >= 0 && s.charAt(i) == '#'){
int backCount = 2;
while(backCount > 0){
i--;
backCount--;
if(i >= 0 && s.charAt(i) == '#'){
backCount+= 2;
}
}
}
if(j >= 0 && t.charAt(j) == '#'){
int backCount = 2;
while(backCount > 0){
j--;
backCount--;
if(j >= 0 && t.charAt(j) == '#'){
backCount+= 2;
}
}
}
}
else{
if(i < 0 || j < 0){
return false;
}
if(s.charAt(i) != t.charAt(j)) {
return false;
} else {
i--;
j--;
}
}
}
return true;
}
}
Python Solution
class Solution:
def get_next_char(self, str1, curr_pos):
curr_pos -= 1
if curr_pos == -1:
return '', -1
char = str1[curr_pos]
count = 0
if char != '#':
return char, curr_pos
count = 2
while count != 0:
curr_pos -= 1
# Access one character
if curr_pos < 0:
return '', -1
char = str1[curr_pos]
# Reduce count after moving 1 character
count -= 1
if char != '#':
continue
count += 2
return char, curr_pos
def backspaceCompare(self, str1, str2):
str1_ptr = len(str1)
str2_ptr = len(str2)
while str1_ptr >= 0 or str2_ptr >= 0:
char1, str1_ptr = self.get_next_char(str1, str1_ptr)
char2, str2_ptr = self.get_next_char(str2, str2_ptr)
if char1 != char2:
return False
return True
==================
var backspaceCompare = function (s, t) {
let p1 = s.length - 1;
let p2 = t.length - 1;
let skipS = 0;
let skipT = 0;
while (p1 >= 0 || p2 >= 0) {
while (p1 >= 0) {
if (s[p1] === "#") {
skipS++;
p1--;
} else if (skipS > 0) {
skipS--;
p1--;
} else break;
}
while (p2 >= 0) {
if (t[p2] === "#") {
skipT++;
p2--;
} else if (skipT > 0) {
skipT--;
p2--;
} else break;
}
// If two actual characters are different
if (p1 >= 0 && p2 >= 0 && s[p1] !== t[p2]) return false;
// If expecting to compare char vs nothing
if (p1 >= 0 !== p2 >= 0) return false;
p1--;
p2--;
Copied!
}
return true;
};
===========================
Python solution, you have to account for negative indexes:
def solution(s: str, t: str) -> bool:
def skip_deleted(string: str, idx: int, to_delete: int) -> int:
"""Skips characters that need to be deleted, by shifting index."""
while to_delete > 0 and idx > -1:
idx -= 1
to_delete -= 1
if string[idx] == '#':
to_delete += 2
return idx
string1, string2 = s, t # to follow PEP8 further down
idx1, idx2 = len(string1) - 1, len(string2) - 1
while idx1 >= 0 or idx2 >= 0:
if (
string1[idx1] == '#' and idx1 >= 0
or string2[idx2] == '#' and idx2 >= 0
):
# need to 'delete' characters
# while we have not fully traversed the string
if string1[idx1] == '#':
idx1 = skip_deleted(string1, idx1, 2)
if string2[idx2] == '#':
idx2 = skip_deleted(string2, idx2, 2)
if idx1 < 0 and idx2 < 0:
# both string are empty after 'deletions'
return True
else:
# Now characters are not '#', so we can compare them
if idx1 < 0 and idx2 >= 0 or idx1 >= 0 and idx2 < 0:
# If one string is "deleted" and other is not, then
# they are not equal
return False
if string1[idx1] != string2[idx2]:
return False
idx1 -= 1
idx2 -= 1
return True
=================================
I find this solution very hard to read and would be also hard to maintain.
Here is my Kotlin solution
tailrec fun findNextCharacterIndex(s: String, index: Int, delCount: Int = 0): Int {
if (index < 0) return -1
if (s[index] == '#') return findNextCharacterIndex(s, index - 1, delCount + 1)
if (delCount > 0) return findNextCharacterIndex(s, index - 1, delCount - 1)
return index
}
fun backspaceCompare(s: String, t: String): Boolean {
var si = findNextCharacterIndex(s, s.length - 1)
var ti = findNextCharacterIndex(t, t.length - 1)
while (si >= 0 && ti >= 0) {
if (s[si] != t[ti]) return false
si = findNextCharacterIndex(s, si - 1)
ti = findNextCharacterIndex(t, ti - 1)
}
return si == ti
}
=================================
def compare_strings(s1, s2):
s1_final = ""
s2_final = ""
for i in range(len(s1)):
if s1[i] == '#':
s1_final = s1_final[:-1]
continue
s1_final += s1[i]
for i in range(len(s2)):
if s2[i] == '#':
s2_final = s2_final[:-1]
continue
s2_final += s2[i]
return s1_final == s2_final
Top comments (0)