[LeetCode]844. Backspace String Compare 解题报告(C++)

题目描述

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

Example 1:

Input: S = "ab#c", T = "ad#c"Output: trueExplanation: Both S and T become "ac".

Example 2:

Input: S = "ab##", T = "c#d#"Output: trueExplanation: Both S and T become "".

Example 3:

Input: S = "a##c", T = "#a#c"Output: trueExplanation: Both S and T become "c".

Example 4:

Input: S = "a#c", T = "b"Output: falseExplanation: S becomes "c" while T becomes "b".

Note:

1 <= S.length <= 2001 <= T.length <= 200SandTonly contain lowercase letters and'#'characters.

题目大意

#表示删除符号. 检查两个字符串是否相同.

解题思路

方法1:

利用栈.将两个字符串真实的样子.再做比较.

代码实现:

class Solution0{public:bool backspaceCompare(string S, string T) {stack<char> s1;stack<char> s2;for (auto x : S) {if (x == '#') {if (!s1.empty()) {s1.pop();}else {continue;}}else {s1.push(x);}}for (auto x : T) {if (x == '#') {if (!s2.empty()) {s2.pop();}else{continue;}}else {s2.push(x);}}if (s1.size() != s2.size()) {return false;}else {while (s1.size() && s2.size()) {if (s1.top() != s2.top()) {return false;}s1.pop();s2.pop();}}return true;}};

方法2:

对方法1优化.使用String做为栈!!!最后比较只用一句即可!!!

代码实现:

class Solution{public:bool backspaceCompare(string S, string T) {string a = "", b = "";for (auto c : S) c == '#' ? a.size() > 0 ? a.pop_back() : void() : a.push_back(c);for (auto c : T) c == '#' ? b.size() > 0 ? b.pop_back() : void() : b.push_back(c);return a == b;}};

方法3:

leetcode高分方法!!!从末尾向前遍历.. 主要看看别人是怎么写 跳过字符的!!! 用for循环统计. 非常溜!!!

代码实现:

class Solution {public:bool backspaceCompare(string S, string T) {int len1 = S.size();int len2 = T.size();for (int i = len1 - 1, j = len2 - 1; ; i--, j--) {for (int b = 0; i >= 0 && (b || S[i] == '#'); --i) {b += S[i] == '#' ? 1 : -1;}for (int b = 0; j >= 0 && (b || T[j] == '#'); --j) {b += T[j] == '#' ? 1 : -1;}if (i < 0 || j < 0 || S[i] != T[j]) {return i == -1 && j == -1;}}}};// 或者这个版本class Solution3 {public:bool backspaceCompare(string S, string T) {int i = S.size() - 1, j = T.size() - 1, countA = 0, countB = 0;while (i >= 0 || j >= 0) {while (i >= 0 && (S[i] == '#' || countA > 0)) S[i--] == '#' ? countA++ : countA--;while (j >= 0 && (T[j] == '#' || countB > 0)) T[j--] == '#' ? countB++ : countB--;if (i < 0 || j < 0) return i == j;if (S[i--] != T[j--]) return false;}return i == j;}};

如果觉得《[LeetCode]844. Backspace String Compare 解题报告(C++)》对你有帮助，请点赞、收藏，并留下你的观点哦！