Try   HackMD

day_09: Backspace String Compare

tags: online_judge, python3

給定兩個只包含字母和#的字串,其中#代表 backspace,問兩個字串在處理完 backspace 後一否一致。

從字串末尾開始掃描,即可把 backspace 轉化為 delete,這時候就變成遇到#就無視下一個字元了。 然而#可能會連續出現,所以需要記錄#連續出現多少次,然後無視同樣多個字元。


題目

Given two strings S and T, return 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 = "#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 <= 200
    1 <= T.length <= 200
    S and T only contain lowercase letters and '#' characters.

Follow up:

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

解答

class Solution: def backspaceCompare(self, S, T): S += "a" T += "a" i = len(S) -1 j = len(T) -1 while i > -1 and j > -1: if S[i] != T[j]: return False S_backspace = 1 while S_backspace > 0 and i > -1: i -= 1 S_backspace -= 1 if S[i] == "#": S_backspace += 2 T_backspace = 1 while T_backspace > 0 and j > -1: j -= 1 T_backspace -= 1 if T[j] == "#": T_backspace += 2 while i > -1 and S[i] == "#": S_backspace = 1 while S_backspace > 0 and i > -1: i -= 1 S_backspace -= 1 if S[i] == "#": S_backspace += 2 while j > -1 and T[j] == "#": T_backspace = 1 while T_backspace > 0 and j > -1: j -= 1 T_backspace -= 1 if T[j] == "#": T_backspace += 2 """print(S[i]) print(T[j])""" if i < 0 and j < 0: return True else: return False a = Solution() print (a.backspaceCompare("ab#c","ad#c")) print (a.backspaceCompare("ab##","c#d#")) print (a.backspaceCompare("a##c","#a#c")) print (a.backspaceCompare("a#c","b")) print (a.backspaceCompare("bxj##tw","bxo#j##tw"))

成績