【LeetCode】 844. Backspace String Compare

Description

Given two strings S and T, return if they are equal when both are typed into empty text editors. # means a backspace character.
Note:
1 <= S.length <= 200
1 <= T.length <= 200
S and T only contain lowercase letters and '#' characters.

給兩個字串S和T，回傳他們是否相同。#符號代表一個倒退字元(Backspace鍵)。
注意：
S和T長度都介於1到200
S和T只會包含小寫字母和'#'符號。

Example:

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 = "#a#c"
Output: true
Explanation: Both S and T become "c".


Example 4:

Input: S = "a#c", T = "b"
Output: false
Explanation: S becomes "c" while T becomes "b".

Solution

• 這題如果只是要解題超級簡單，你慢慢硬爆也可以，但是我們要挑戰時間複雜度為O(N)和空間複雜度O(1)。
  • 也就是說，不能有雙重for loop也不能產生額外的陣列去存新的字串來處理。
• 既然不能開額外的字串，那麼我們就要直接對原字串S和T處理。
• 我建議從尾巴往回看:
  • 優點是for的判斷式不會因為erase亂掉，且不用處理多餘的#。
  • 缺點是要另外記錄現在有多少#還沒使用，以免在連續的#發生錯誤。

Code

class Solution {
public:
    bool backspaceCompare(string S, string T) {
        int count = 0;
        for(int i = S.size() - 1; i >= 0; i--)
            if(S[i] == '#')
            {
                S.erase(S.begin() + i);
                count++;
            }
            else if(count > 0)
            {
                S.erase(S.begin() + i);
                count--;
            }
        count = 0;
        for(int i = T.size() - 1; i >= 0; i--)
            if(T[i] == '#') 
            {
                T.erase(T.begin() + i);
                count++;
            }
            else if(count > 0)
            {
                T.erase(T.begin() + i);
                count--;
            }
        return S == T;
    }
};

tags: LeetCode C++