題目： LeetCode - 844. Backspace String Compare

題目說明

給兩個字串，模擬字串的內容操作鍵盤，字串內的 # 代表 BackSpace，判斷模擬完後輸出的字串是否相同。

解題思路

  • 解法一：定義新的兩個 String 並分別遍歷原本的字串，若不是 # 則 push_back() 到新字串，否則就 pop_back()。( 須注意字串的Size，若是 0 就不能在 pop_back() )

  • 解法二：使用雙指針，將模擬操作後的字串放入原本的字串。( 一樣要注意 Size 的問題 )

參考解法

解法一：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    bool backspaceCompare(string S, string T) {
        string s, t;
        
        for(auto& i : S)
            if( i != '#')
                s.push_back(i);
            else if(s.size() > 0)
                s.pop_back();
        
        for(auto& i : T)
            if( i != '#')
                t.push_back(i);
            else if(t.size() > 0)
                t.pop_back();
        
        return (s == t);
    }
};

解法二：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    bool backspaceCompare(string S, string T) {
        int pos = 0; 
        for(auto& i : S)
            if(i != '#')
                S[pos] = i, ++pos;
            else if(pos > 0)
                --pos;
        S.resize(pos);
        
        pos = 0;
        for(auto& i : T)
            if(i != '#')
                T[pos] = i, ++pos;
            else if(pos > 0)
                --pos;
        T.resize(pos);
        
        return (S == T);
    }
};