Karl's Nest
0%

leetcode-day-9

Posted on In
Day-9 Backspace String Compare

LeetCode 30 days Challenge - Day 9

本系列将对LeetCode新推出的30天算法挑战进行总结记录，旨在记录学习成果、方便未来查阅，同时望为广大网友提供帮助。

Backspace String Compare

Given two strings S and T, return if they are equal when both are typed into empty text editors. # means a backspace character.

Example 1:

1
2
3
Input: S = "ab#c", T = "ad#c"
Output: true
Explanation: Both S and T become "ac".

Example 2:

1
2
3
Input: S = "ab##", T = "c#d#"
Output: true
Explanation: Both S and T become "".

Example 3:

1
2
3
Input: S = "a##c", T = "#a#c"
Output: true
Explanation: Both S and T become "c".

Example 4:

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

Note:

  1. 1 <= S.length <= 200
  2. 1 <= T.length <= 200
  3. S and T only contain lowercase letters and '#' characters.

Follow up:

  • Can you solve it in O(N) time and O(1) space?

Solution

题目要求分析：给定两个字符串，其中“#”号表示一个退格，要求判断处理完退格操作后两个字符串是否相同。

解法：

本题是栈结构的经典应用，以下分析模拟操作的原则：

  1. 遍历字符串，遇到不为退格“#”的字符，压栈。
  2. 遇到退格“#”时：
    1. 若栈为空，忽略（空字符串怎么进行退格依然为空）。
    2. 反之，将栈顶元素退栈（相当于退格当前字符串的最后一个字符）。
  3. 对两个字符串处理完成后，依次退栈比较：
    1. 遇到不相同的字符，则返回false。
    2. 比较到栈空，返回true。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
bool backspaceCompare(string S, string T) {
    stack<char> s, t;
    for (char c : S) {
        if (c == '#' && !s.empty()) s.pop();
        else if (c != '#') s.push(c);
    }
    for (char c : T) {
        if (c == '#' && !t.empty()) t.pop();
        else if (c != '#') t.push(c);
    }
    while (!s.empty() && !t.empty()) {
        if (s.top() != t.top()) return false;
        s.pop(); t.pop();
    }
    return (s.empty() && t.empty());
}

传送门：Backspace String Compare

Karl