LeetCode 844: Backspace String Compare (Two Pointers)
LeetCode 844StringTwo PointersToday we solve LeetCode 844 - Backspace String Compare.
Source: https://leetcode.com/problems/backspace-string-compare/
English
Problem Summary
Given two strings s and t, where # means backspace, determine whether the two strings are equal after applying all backspaces.
Key Insight
Scan from right to left with two pointers. When you see #, increase a skip counter; when you see a normal character while skip > 0, consume it. The next remaining character on each side is the real typed character to compare.
Brute Force and Limitations
A straightforward approach builds final strings using stacks/StringBuilder and compares them. It works in O(n) time, but uses extra O(n) space.
Optimal Algorithm Steps
1) Set i = s.length - 1, j = t.length - 1.
2) Move i to the next valid char in s (skip deleted chars).
3) Move j similarly in t.
4) If both valid chars exist, compare them; if different, return false.
5) If only one side has chars left, return false; otherwise continue until both finish.
Complexity Analysis
Time: O(n + m), each character is visited at most once.
Space: O(1), only pointers and counters.
Common Pitfalls
- Forgetting to process consecutive # (e.g. "ab###").
- Comparing characters before fully skipping deleted ones.
- Not handling the case where one pointer is exhausted first.
Reference Implementations (Java / Go / C++ / Python / JavaScript)
class Solution {
public boolean backspaceCompare(String s, String t) {
int i = s.length() - 1, j = t.length() - 1;
while (i >= 0 || j >= 0) {
i = nextValidIndex(s, i);
j = nextValidIndex(t, j);
if (i >= 0 && j >= 0) {
if (s.charAt(i) != t.charAt(j)) return false;
i--;
j--;
} else {
return i == j;
}
}
return true;
}
private int nextValidIndex(String str, int idx) {
int skip = 0;
while (idx >= 0) {
char c = str.charAt(idx);
if (c == '#') {
skip++;
idx--;
} else if (skip > 0) {
skip--;
idx--;
} else {
break;
}
}
return idx;
}
}func backspaceCompare(s string, t string) bool {
i, j := len(s)-1, len(t)-1
for i >= 0 || j >= 0 {
i = nextValidIndex(s, i)
j = nextValidIndex(t, j)
if i >= 0 && j >= 0 {
if s[i] != t[j] {
return false
}
i--
j--
} else {
return i == j
}
}
return true
}
func nextValidIndex(str string, idx int) int {
skip := 0
for idx >= 0 {
if str[idx] == '#' {
skip++
idx--
} else if skip > 0 {
skip--
idx--
} else {
break
}
}
return idx
}class Solution {
public:
bool backspaceCompare(string s, string t) {
int i = (int)s.size() - 1;
int j = (int)t.size() - 1;
while (i >= 0 || j >= 0) {
i = nextValidIndex(s, i);
j = nextValidIndex(t, j);
if (i >= 0 && j >= 0) {
if (s[i] != t[j]) return false;
--i;
--j;
} else {
return i == j;
}
}
return true;
}
private:
int nextValidIndex(const string& str, int idx) {
int skip = 0;
while (idx >= 0) {
if (str[idx] == '#') {
++skip;
--idx;
} else if (skip > 0) {
--skip;
--idx;
} else {
break;
}
}
return idx;
}
};class Solution:
def backspaceCompare(self, s: str, t: str) -> bool:
i, j = len(s) - 1, len(t) - 1
while i >= 0 or j >= 0:
i = self.next_valid_index(s, i)
j = self.next_valid_index(t, j)
if i >= 0 and j >= 0:
if s[i] != t[j]:
return False
i -= 1
j -= 1
else:
return i == j
return True
def next_valid_index(self, string: str, idx: int) -> int:
skip = 0
while idx >= 0:
if string[idx] == '#':
skip += 1
idx -= 1
elif skip > 0:
skip -= 1
idx -= 1
else:
break
return idxfunction backspaceCompare(s, t) {
let i = s.length - 1;
let j = t.length - 1;
while (i >= 0 || j >= 0) {
i = nextValidIndex(s, i);
j = nextValidIndex(t, j);
if (i >= 0 && j >= 0) {
if (s[i] !== t[j]) return false;
i--;
j--;
} else {
return i === j;
}
}
return true;
}
function nextValidIndex(str, idx) {
let skip = 0;
while (idx >= 0) {
if (str[idx] === '#') {
skip++;
idx--;
} else if (skip > 0) {
skip--;
idx--;
} else {
break;
}
}
return idx;
}中文
题目概述
给定两个字符串 s 和 t，其中 # 表示退格，判断它们在执行所有退格后是否相同。
核心思路
从右往左双指针扫描：遇到 # 就增加“待删除计数”，遇到普通字符且计数 > 0 就跳过。这样每次拿到的都是“最终真正保留”的字符。
暴力解法与不足
朴素做法是用栈或 StringBuilder 分别还原两个字符串，再比较结果。时间 O(n)，但需要额外 O(n) 空间。
最优算法步骤
1）初始化 i = s.length - 1、j = t.length - 1。
2）把 i 移到 s 的下一个有效字符。
3）把 j 移到 t 的下一个有效字符。
4）若两边都有效则比较字符，不同直接 false。
5）若仅一边还有字符，false；两边都结束则 true。
复杂度分析
时间复杂度：O(n + m)，每个字符最多访问一次。
空间复杂度：O(1)，只用指针和计数器。
常见陷阱
- 连续多个 # 处理不完整（如 "ab###"）。
- 还没跳过被删除字符就提前比较。
- 一侧先结束时没有正确返回 false。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
class Solution {
public boolean backspaceCompare(String s, String t) {
int i = s.length() - 1, j = t.length() - 1;
while (i >= 0 || j >= 0) {
i = nextValidIndex(s, i);
j = nextValidIndex(t, j);
if (i >= 0 && j >= 0) {
if (s.charAt(i) != t.charAt(j)) return false;
i--;
j--;
} else {
return i == j;
}
}
return true;
}
private int nextValidIndex(String str, int idx) {
int skip = 0;
while (idx >= 0) {
char c = str.charAt(idx);
if (c == '#') {
skip++;
idx--;
} else if (skip > 0) {
skip--;
idx--;
} else {
break;
}
}
return idx;
}
}func backspaceCompare(s string, t string) bool {
i, j := len(s)-1, len(t)-1
for i >= 0 || j >= 0 {
i = nextValidIndex(s, i)
j = nextValidIndex(t, j)
if i >= 0 && j >= 0 {
if s[i] != t[j] {
return false
}
i--
j--
} else {
return i == j
}
}
return true
}
func nextValidIndex(str string, idx int) int {
skip := 0
for idx >= 0 {
if str[idx] == '#' {
skip++
idx--
} else if skip > 0 {
skip--
idx--
} else {
break
}
}
return idx
}class Solution {
public:
bool backspaceCompare(string s, string t) {
int i = (int)s.size() - 1;
int j = (int)t.size() - 1;
while (i >= 0 || j >= 0) {
i = nextValidIndex(s, i);
j = nextValidIndex(t, j);
if (i >= 0 && j >= 0) {
if (s[i] != t[j]) return false;
--i;
--j;
} else {
return i == j;
}
}
return true;
}
private:
int nextValidIndex(const string& str, int idx) {
int skip = 0;
while (idx >= 0) {
if (str[idx] == '#') {
++skip;
--idx;
} else if (skip > 0) {
--skip;
--idx;
} else {
break;
}
}
return idx;
}
};class Solution:
def backspaceCompare(self, s: str, t: str) -> bool:
i, j = len(s) - 1, len(t) - 1
while i >= 0 or j >= 0:
i = self.next_valid_index(s, i)
j = self.next_valid_index(t, j)
if i >= 0 and j >= 0:
if s[i] != t[j]:
return False
i -= 1
j -= 1
else:
return i == j
return True
def next_valid_index(self, string: str, idx: int) -> int:
skip = 0
while idx >= 0:
if string[idx] == '#':
skip += 1
idx -= 1
elif skip > 0:
skip -= 1
idx -= 1
else:
break
return idxfunction backspaceCompare(s, t) {
let i = s.length - 1;
let j = t.length - 1;
while (i >= 0 || j >= 0) {
i = nextValidIndex(s, i);
j = nextValidIndex(t, j);
if (i >= 0 && j >= 0) {
if (s[i] !== t[j]) return false;
i--;
j--;
} else {
return i === j;
}
}
return true;
}
function nextValidIndex(str, idx) {
let skip = 0;
while (idx >= 0) {
if (str[idx] === '#') {
skip++;
idx--;
} else if (skip > 0) {
skip--;
idx--;
} else {
break;
}
}
return idx;
}
Comments