Skip to content
Coding

LeetCode 844. Backspace String Compare

By Anthea / 芫荽 2 min read
LeetCode 844. Backspace String Compare
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:

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 = "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?

暴力解

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

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" 為例：

// Run 1 
// sIndex = 6 
// tIndex = 7 
var currentS = 'p'; 
var currentT = 'p'; 
 
// currentS == currentT : true 
// PASS
// 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;

寫成程式碼：

// 從最後一個字母開始比對 
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

參考資料