844. Backspace String Compare

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?

解題

使用 stack 來做消除的動作

Runtime: 0 ms, faster than 100%

Memory Usage: 2 MB, less than 87.44%

func backspaceCompare(s string, t string) bool {
    sstack := make([]byte, 0)
    tstack := make([]byte, 0)
    
    for i:=0; i<len(s); i++ {
        if  s[i] == '#' {
            if len(sstack) != 0  {
                sstack = sstack[:len(sstack) - 1]
            }
        } else {
            sstack = append(sstack, s[i])
        }
    }

    for i:=0; i<len(t); i++ {
        if  t[i] == '#' {
            if len(tstack) != 0  {
                tstack = tstack[:len(tstack) - 1]
            }
        } else {
            tstack = append(tstack, t[i])
        }
    }


    return string(sstack) == string(tstack)
}