Problem
题目大意：给你2个字符串表示打字顺序，判断它们的结果是否相同，’#’表示退格键。
https://leetcode.com/problems/backspace-string-compare/description/
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:
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 = "#a#c" Output: true Explanation: Both S and T become "c".
Example 4:
Input: S = "a#c", T = "b" Output: false Explanation: S becomes "c" while T becomes "b".
Note:
1 <= S.length <= 2001 <= T.length <= 200SandTonly contain lowercase letters and'#'characters.
Solution: Simulation
Time complexity: O(|S| + |T|)
Space complexity: O(|S| + |T|)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
// Author: Huahua // Running time: 5 ms class Solution { public: bool backspaceCompare(string S, string T) { return type(S) == type(T); } private: string type(string S) { string o; for (char c : S) if (c == '#') { if (!o.empty()) o.pop_back(); } else { o.push_back(c); } return o; } }; |
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
// Author: Huahua, 7 ms class Solution { public boolean backspaceCompare(String S, String T) { return type(S).equals(type(T)); } private String type(String s) { StringBuilder sb = new StringBuilder(); for (char c : s.toCharArray()) { if (c == '#') { if (sb.length() > 0) sb.setLength(sb.length() - 1); } else { sb.append(c); } } return sb.toString(); } } |
Python3
|
1 2 3 4 5 6 7 8 9 10 11 12 |
# Author: Huahua, 40 ms class Solution: def backspaceCompare(self, S, T): def sim(S): ans = '' for c in S: if c == '#': if len(ans) > 0: ans = ans[:-1] else: ans += c return ans return sim(S) == sim(T) |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Paypal
Venmo
huahualeetcode
huahualeetcode
微信打赏
Be First to Comment