> ## Content Index
> Fetch the complete content index at: https://blog.anthea.day/llms.txt
> Use this file to discover other available public pages before exploring further.

# LeetCode 844. Backspace String Compare
- URL: https://blog.anthea.day/leetcode-c-e5-88-b7-e9-a1-8c-e7-ad-86-e8-a8-98-10/
- Published: 2023-01-01T13:37:44.000Z
- Updated: 2026-11-07T18:26:16.000Z
- Author: Anthea / 芫荽
- Tags: #Migrated-1792241843742, #Import 2026-10-17 12:57, Coding, LeetCode 刷題筆記

> 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:**

```vbnet
Input: s = "ab#c", t = "ad#c" 
Output: true 
Explanation: Both s and t become "ac".
```

**Example 2:**

```vbnet
Input: s = "ab##", t = "c#d#" 
Output: true 
Explanation: Both s and t become "".
```

**Example 3:**

```vbnet
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?

---

### 暴力解

把結果塞進字串裡，遇到 `#` 就刪掉一個字元。

```perl
var sResult = ""; 
var tResult = ""; 
var index = 0; 
 
while (index < s.Length || index < t.Length) 
{ 
    if (index < s.Length) 
    { 
        if (s[index] == '#') 
        { 
            if (sResult != "") 
            { 
                sResult = sResult.Remove(sResult.Length - 1); 
            } 
        } 
        else 
        { 
            sResult += s[index]; 
        } 
    } 
 
    if (index < t.Length) 
    { 
        if (t[index] == '#') 
        { 
            if (tResult != "") 
            { 
                tResult = tResult.Remove(tResult.Length - 1); 
            } 
        } 
        else 
        { 
            tResult += t[index]; 
        } 
    } 
     
    index++; 
} 
 
return sResult == tResult;
```

#### 效能

- Time complexity - `O(n)`
- Space complexity - `O(n)`
- Runtime - 78 ms
- Memory - 38.8 MB

---

### 最佳解

從最後一個字母開始比。

以 `s = "xywrrmp",t = "xywrrm#p"` 為例：

```csharp
// Run 1 
// sIndex = 6 
// tIndex = 7 
var currentS = 'p'; 
var currentT = 'p'; 
 
// currentS == currentT : true 
// PASS
```

```kotlin
// Run 2 
// sIndex = 5 
// tIndex = 6 
var currentS = 'm'; 
var currentT = '#'; 
 
// currentT == '#' : Backspace 
// 有需要被消除的字母時把 Index 往前移 (m 會被 # 消掉) 
// tIndex = 4 
currentT = 'r'; 
 
// currentS == currentT : false 
// (sywrrmp)   (xywrrp) 
return false;
```

寫成程式碼：

```kotlin
// 從最後一個字母開始比對 
var sIndex = s.Length - 1; 
var tIndex = t.Length - 1; 
 
// 有需要被消除的字母數量 
var skipCountInS = 0; 
var skipCountInT = 0; 
 
while(true) 
{ 
    while(sIndex >= 0) 
    { 
        if (s[sIndex] == '#') 
        { 
            skipCountInS++; 
        } 
        else 
        { 
            if (skipCountInS > 0) 
            { 
                skipCountInS--; 
            } 
            else 
            { 
                // 沒有需要被消除的字母時跳出迴圈 
                break; 
            } 
        } 
 
        // 有需要被消除的字母時把 Index 往前移 
        sIndex--; 
    } 
 
    while(tIndex >= 0) 
    { 
        if (t[tIndex] == '#') 
        { 
            skipCountInT++; 
        } 
        else 
        { 
            if (skipCountInT > 0) 
            { 
                skipCountInT--; 
            } 
            else 
            { 
                // 沒有需要被消除的字母時跳出迴圈 
                break; 
            } 
        } 
 
        // 有需要被消除的字母時把 Index 往前移 
        tIndex--; 
    } 
 
    // 如果 Index < 0 代表遍歷完成 
    if (sIndex < 0 || tIndex < 0) break; 
 
    // 如果 current 不相等 
    if (s[sIndex] != t[tIndex]) return false; 
 
    // 繼續比對下一個字母 
    sIndex--; 
    tIndex--; 
} 
 
// 如果 Index != -1 代表長度不一致，沒有遍歷完成 
return sIndex == -1 && tIndex == -1;
```

#### 效能

- Time complexity - `O(n)`
- Space complexity - `O(1)`
- Runtime - 73 ms
- Memory - 38 MB

---

#### 參考資料

- [844\. Backspace String Compare](https://leetcode.com/problems/backspace-string-compare/description/?ref=blog.anthea.day)
- [代碼隨想錄：0844.比較含退格的字符串](https://github.com/youngyangyang04/leetcode-master/blob/master/problems/0844.%E6%AF%94%E8%BE%83%E5%90%AB%E9%80%80%E6%A0%BC%E7%9A%84%E5%AD%97%E7%AC%A6%E4%B8%B2.md?ref=blog.anthea.day)