Problem

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.

Examples

Example 1:

1
2
3

Input: s = "ab#c", t = "ad#c"
Output: true
Explanation: Both s and t become "ac".

Example 2:

1
2
3

Input: s = "ab##", t = "c#d#"
Output: true
Explanation: Both s and t become "".

Example 3:

1
2
3

Input: s = "a#c", t = "b"
Output: false
Explanation: s becomes "c" while t becomes "b".

Solution

Method 1 - Iterative From End of String

Backspace # affects the string, for eg. ab## becomes "". When we move from left to right in string, say with iterator index i, and if we encounter #, we have to come back.

What if traverse backwards. Whenever we encounter #, we skip some chars, depending on number of # we encountered. Otherwise, we will just compare 2 strings.

Code

 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
43
44
45
46

public boolean backspaceCompare(String s, String t) {
	int i = s.length() - 1, j = t.length() - 1;
	int skipS = 0, skipT = 0;

	// While there may be chars in build(s) or build (t)
	while (i >= 0 || j >= 0) {
		// Find position of next possible char in build(s)
		while (i >= 0) {
			if (s.charAt(i) == '#') {
				skipS++;
				i--;
			} else if (skipS > 0) {
				skipS--;
				i--;
			} else {
				break;
			}
		}
		// Find position of next possible char in build(t)
		while (j >= 0) { 
			if (t.charAt(j) == '#') {
				skipT++;
				j--;
			} else if (skipT > 0) {
				skipT--;
				j--;
			} else {
				break;
			}
		}

		// If two actual characters are different
		if (i >= 0 && j >= 0 && s.charAt(i) != t.charAt(j)) {
			return false;
		}
		// If expecting to compare char vs nothing
		if (((i >= 0) && (j == -1)) || ((i == -1) && j >= 0)) {
			return false;
		}

		i--;
		j--;
	}

	return true;
}