Simulation Stack String Two Pointers
Description 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.
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".
Constraints:
1 <= s.length, t.length <= 200 s and t only contain lowercase letters and '#' characters.
Follow up: Can you solve it in O(n) time and O(1) space?
Solutions Solution 1 Thinking
We compare two strings after applying backspaces. Building the cleaned strings uses extra linear space; the intended scan works on the originals.
Walk right to left, letting a skip counter consume # and the characters they delete, then compare the next live characters. If one side runs out first, they differ.
Python3 Java C++ Go TypeScript Rust
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29 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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38 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 ;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34 class Solution {
public :
bool backspaceCompare ( string s , string t ) {
int i = s . size () - 1 , j = t . size () - 1 ;
int skip1 = 0 , skip2 = 0 ;
for (; i >= 0 || j >= 0 ; -- i , -- j ) {
while ( i >= 0 ) {
if ( s [ i ] == '#' ) {
++ skip1 ;
-- i ;
} else if ( skip1 ) {
-- skip1 ;
-- i ;
} else
break ;
}
while ( j >= 0 ) {
if ( t [ j ] == '#' ) {
++ skip2 ;
-- j ;
} else if ( skip2 ) {
-- 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 ;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36 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
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34 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 ;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42 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
}
}
GitHub 