描述
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:
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 = "#a#c" Output: true Explanation: Both S and T become "c".
|
Example 4:
1 2 3
| 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.
Follow up:
- Can you solve it in
O(N)
time and O(1)
space?
分析
可以用先进后出的栈的思想来解决这个问题。
解决方案1(Java)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
| class Solution { public boolean backspaceCompare(String S, String T) { return realStr(S).equals(realStr(T)); } private String realStr(String s) { StringBuilder result = new StringBuilder(); for (char c: s.toCharArray()) { if (c == '#') { if (result.length() > 0) { result.setLength(result.length() - 1); } } else { result.append(c); } } return result.toString(); } }
|