Backspace String Compare
Given two strings containing backspace characters, compare the final strings after applying the backspace operations.
Constraints:
- 1 <= s.length, t.length <= 200
- s and t only contain lowercase letters and '#' characters.
Examples:
Input: "ab#c","ad#c"
Output: true
Explanation: Applying the backspace operations, we get "ac" for both strings.
Solutions
Two-Pointer Approach
Time: O(n + m)Space: O(n + m)
We use a two-pointer approach to build the final strings after applying the backspace operations. We iterate through each string, and whenever we encounter a '#', we remove the last character from the string if it's not empty.
public boolean backspaceCompare(String s, String t) {
return build(s).equals(build(t));
}
public String build(String s) {
StringBuilder sb = new StringBuilder();
for (char c : s.toCharArray()) {
if (c != '#') {
sb.append(c);
}
else if (sb.length() > 0) {
sb.deleteCharAt(sb.length() - 1);
}
}
return sb.toString();
}Follow-up:
How would you optimize the solution if the input strings are very large?
