## Debug School

rakesh kumar

Posted on • Updated on

# String:typed out string

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
``````