Last Updated on 2022-05-01 by Clay
題目
Given two strings s and t, return true 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 = "b" Output: false Explanation: s becomes "c" while t becomes "b".
Constraints:
1 <= s.length, t.length <= 200sandtonly contain lowercase letters and'#'characters.
Follow up: Can you solve it in O(n) time and O(1) space?
題目輸入兩組字串，字串中的字元依序為輸入的順序，但如果字元為 # ，則表示在此輸入了刪除鍵（backspace）；如果前一個字元存在，則刪除它。
最後，我們需要判斷兩組字串的結果是否相同。
解題思路
Stack 解法
使用 stack 可以說是最直覺的解法了，不過其實完成不了 follow-up 的要求。
基本上就是建立 stack，依序將字元推入，在遇到刪除符號 # 時則將 stack 中的字元彈出。
最後，則直接比較兩 stack 間是否相同。
Stack 解法複雜度
| Time complexity | O(n) |
| Space complexity | O(n) |
Stack 解法 C++ 範例程式碼
class Solution {
public:
bool backspaceCompare(string s, string t) {
// Init
stack<char> st_s;
stack<char> st_t;
// Complete
for (char c: s) {
if (c == '#') {
if (!st_s.empty()) {
st_s.pop();
}
}
else {
st_s.push(c);
}
}
for (char c: t) {
if (c == '#') {
if (!st_t.empty()) {
st_t.pop();
}
}
else {
st_t.push(c);
}
}
return st_s == st_t;
}
};Stack 解法 Python 範例程式碼
class Solution:
def backspaceCompare(self, s: str, t: str) -> bool:
# Init
st_s = []
st_t = []
# Complete s stack
for c in s:
if c == '#':
if st_s != []:
st_s.pop()
else:
st_s.append(c)
# Complete t stack
for c in t:
if c == '#':
if st_t != []:
st_t.pop()
else:
st_t.append(c)
return st_s == st_t優化解法
若要完成 follow-up 的要求，我們可以嘗試對於兩個字串分別計算一個特殊的索引，在這裡就稱為 si 和 ti。
當我們遍歷確認字元時，如果不為刪除符號 #，則將字元放入原始字串的第 si 或 ti 位置，接著把特殊索引加一，代表下一個字元該放入的下一個位置。
然而，若是遇到了刪除符號 # ，則將特殊索引減一，代表著連上一個字元也不需要紀錄、可被覆蓋了。
等到兩組輸入字串遍歷完成後，再比較 s[0] 到 s[si-1] 和 t[0] 到 t[ti-1] 是否完全一致。
優化解法複雜度
| Time complexity | O(n) |
| Space complexity | O(1) |
優化解法 C++ 範例程式碼
class Solution {
public:
bool backspaceCompare(string s, string t) {
// Init
int si = 0;
int ti = 0;
// Compute the string answer
for (int i=0; i<s.size(); ++i) {
if (s[i] != '#') {
// Move the keep character to the index `si`
s[si] = s[i];
// Increase the string length
++si;
}
// Backspace
else if (si > 0) --si;
}
// Compute the target answer
for (int i=0; i<t.size(); ++i) {
if (t[i] != '#') {
// Move the keep character to the index `ti`
t[ti] = t[i];
// Increase the target length
++ti;
}
// Backspace
else if (ti > 0) --ti;
}
// If length not match
if (si != ti) return false;
for (int i=0; i<si; ++i) {
if (s[i] != t[i]) {
return false;
}
}
return true;
}
};優化解法 Python 範例程式碼
Python 的字串是不可變的…… 所以這個解法參考就好。應該無法像 C++ 那般比前一組解法更優化。
class Solution:
def backspaceCompare(self, s: str, t: str) -> bool:
# Init
s = list(s)
t = list(t)
si = 0
ti = 0
# Compute the string answer
for c in s:
if c != '#':
# Move the keep character to the index `si`
s[si] = c
# Increase the string length
si += 1
# Backspace
elif si > 0:
si -= 1
# Compute the target answer
for c in t:
if c != '#':
# Move the keep character to the index `ti`
t[ti] = c
# Increase the target length
ti += 1
# Backspace
elif ti > 0:
ti -= 1
# If length not match
return s[:si] == t[:ti]