Backspace String Compare
Similar Problems:
Given two strings S and T, return if they are equal when both are typed into empty text editors. # means a backspace character.
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 = "#a#c" Output: true Explanation: Both S and T become "c".
Example 4:
Input: S = "a#c", T = "b" Output: false Explanation: S becomes "c" while T becomes "b".
Note:
- 1 <= S.length <= 200
- 1 <= T.length <= 200
- S and T only contain lowercase letters and ‘#’ characters.
Github: code.dennyzhang.com
Credits To: leetcode.com
Leave me comments, if you have better ways to solve.
- Solution: Time O(n), Space O(n)
// https://code.dennyzhang.com/backspace-string-compare
// Basic Ideas:
// Complexity: Time O(n), Space O(n)
func getString(S string) string {
ret := []string{}
for _, ch := range S {
if ch != '#' {
ret = append(ret, string(ch))
} else {
if len(ret) != 0 { ret = ret[0:len(ret)-1] }
}
}
return strings.Join(ret, "")
}
func backspaceCompare(S string, T string) bool {
return getString(S) == getString(T)
}
