844.Backspace String Compare

发表于 | 更新于 | 分类于 ， | 评论数： | 阅读次数：
字数统计: 240 | 阅读时间 ≈ 1

题目描述

Given two strings S and T, return 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 = “#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”.
Note:

1 <= S.length <= 200
1 <= 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?

我的解法

实现代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    string backspace(string s){
        string res;
        for (char c : s){
            if (c != '#')
                res += c;
            else if (c == '#'){
                res = res.substr(0,res.size()-1);
            }
        }
        return res;
    }
    bool backspaceCompare(string S, string T) {
        return backspace(S) == backspace(T);
    }
};

执行用时：0 ms, 在所有 C++ 提交中击败了100.00%的用户
内存消耗：6.4 MB, 在所有 C++ 提交中击败了35.40%的用户