844. Backspace String Compare

Posted on In Views: 40 Words count: 2.5k Reading time ≈ 2 mins.

844. Backspace String Compare

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

Difficulty : Easy

Solution

Convert the string to char array and use variable i as write index and j as read index

  • if i > 0 and array[j] = ‘#’, i –
  • otherwise, set array[j] to array[i] and increase write index by i
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public boolean backspaceCompare(String s, String t) {
        String a = process(s.toCharArray());
        String b = process(t.toCharArray());
        return a.equals(b);
    }
    
    private String process(char[] array) {
        int i = 0;        
        for (int j = 0; j < array.length; j++) {
            if (array[j] == '#') {
                if (i > 0) {
                    i--;
                }                
            } else {
                array[i++] = array[j];
            }
        }
        return new String(array, 0, i);
    }
}

Solution 2

scan the 2 strings from the back at the same time.
Because after we processed the index i from the back, the value of index i will not be changed anymore.
Also, we don’t need extra space to store the intermediate result during the process.

Time : O(m + n)
Space : O(1)

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
47
48
49
50
51
52
53
54
class Solution {
    /**
    "nzp#o#g"
    "b#nzp#o#g"
    
    */
    public boolean backspaceCompare(String S, String T) {
        
        int m = S.length();
        int n = T.length();
        int i = m - 1;
        int j = n - 1;    
        //这里必须是或，下面这个case，当i=-1 的时候 j还有2个字符要处理
        //"nzp#o#g"
        //"b#nzp#o#g"
        while(i >= 0 || j >= 0) {
            int skipS = 0;
            while(i >= 0) {
                if (S.charAt(i) == '#') {
                    skipS++;
                    i--;
                } else if (skipS > 0) {
                    skipS--;
                    i--;
                } else {
                    break;
                }
            }
            int skipT = 0;
            while (j >= 0) {
                if (T.charAt(j) == '#') {
                    skipT++;
                    j--;
                } else if (skipT > 0) {
                    skipT--;
                    j--;
                } else {
                    break;
                }
            }
            if (i >= 0 && j >= 0 && S.charAt(i) != T.charAt(j)) {
                return false;
            }
            //System.out.println(i+","+j);
            if ((i >= 0) != (j >=0)) {
                return false;
            }
            i--;
            j--;
        }
        
        return true ;
    }
}