Сложность: easy
Даны две строки s и t, верните true, если они равны после ввода в пустые текстовые редакторы. Символ '#' означает клавишу backspace.
Обратите внимание, что после нажатия backspace на пустом тексте, текст останется пустым.
Пример:
Input: s = "ab#c", t = "ad#c"
Output: true
Explanation: Both s and t become "ac".
👨💻 Алгоритм:
1⃣Пройдите по строкам s и t с конца, учитывая символы '#' как backspace и пропуская соответствующие символы.
2⃣Сравнивайте текущие символы из обеих строк, пропуская символы, которые должны быть удалены.
3⃣Если все соответствующие символы совпадают и строки эквивалентны после всех backspace операций, верните true; в противном случае верните false.
😎 Решение:
class Solution {
public:
bool backspaceCompare(string S, string T) {
int i = S.length() - 1, j = T.length() - 1;
int skipS = 0, skipT = 0;
while (i >= 0 || j >= 0) {
while (i >= 0) {
if (S[i] == '#') { skipS++; i--; }
else if (skipS > 0) { skipS--; i--; }
else break;
}
while (j >= 0) {
if (T[j] == '#') { skipT++; j--; }
else if (skipT > 0) { skipT--; j--; }
else break;
}
if (i >= 0 && j >= 0 && S[i] != T[j]) {
return false;
}
if ((i >= 0) != (j >= 0)) {
return false;
}
i--; j--;
}
return true;
}
};Ставь 👍 и забирай 📚 Базу знаний