比较含退格的字符串

阅读数: 次 2020-10-19

语言：C++

IDE：Xcode

问题来源：LeetCode

链接：https://leetcode-cn.com/problems/backspace-string-compare

问题描述

给定S 和T 两个字符串，当它们分别被输入到空白的文本编辑器后，判断二者是否相等，并返回结果。 # 代表退格字符。

注意：如果对空文本输入退格字符，文本继续为空。

示例 1：

1
2
3

输入：S = "ab#c", T = "ad#c"
输出：true
解释：S 和 T 都会变成 “ac”

示例 2：

1
2
3

输入：S = "ab##", T = "c#d#"
输出：true
解释：S 和 T 都会变成 “”

示例 3：

1
2
3

输入：S = "a##c", T = "#a#c"
输出：true
解释：S 和 T 都会变成 “c”

示例 4：

1
2
3

输入：S = "a#c", T = "b"
输出：false
解释：S 会变成 “c”，但 T 仍然是 “b”

代码实现

class Solution {
public:
    bool backspaceCompare(string S, string T) {
        string::iterator itr_begin_S = S.begin();
        string::iterator itr_end_S = S.end()-1;
        string::iterator itr_begin_T = T.begin();
        string::iterator itr_end_T = T.end()-1;
        int time_S = 0;
        int time_T = 0;
        while(*itr_begin_S == '#')
        {
            S.erase(itr_begin_S);
            --itr_end_S;
        }
        while(*itr_begin_T == '#')
        {
            T.erase(itr_begin_T);
            --itr_end_T;
        }
        while(itr_begin_S != itr_end_S)
        {
            while(time_S != 0 && *itr_end_S != '#')
            {
                --time_S;
                S.erase(itr_end_S);
                --itr_end_S;
                if(itr_begin_S == itr_end_S)
                    break;
            }
            if(itr_begin_S == itr_end_S)
                break;
            if(*itr_end_S == '#')
            {
                ++time_S;
                S.erase(itr_end_S);
                --itr_end_S;
                
            }
            else
                --itr_end_S;
        }
        while(itr_begin_T != itr_end_T)
        {
            while(time_T != 0 && *itr_end_T != '#')
            {
                --time_T;
                T.erase(itr_end_T);
                --itr_end_T;
                if(itr_begin_T == itr_end_T)
                    break;
            }
            if(itr_begin_T == itr_end_T)
                break;
            if(*itr_end_T == '#')
            {
                ++time_T;
                T.erase(itr_end_T);
                --itr_end_T;
            }
            else
                --itr_end_T;
        }
        if(itr_begin_S == itr_end_S && time_S != 0)
            S.erase(itr_begin_S);
        if(itr_begin_T == itr_end_T && time_T != 0)
            T.erase(itr_begin_T);
        
        if(S == T)
            return true;
        else
            return false;
    }
};