Q:
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 <= 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?
A:
就是从后往前比较, 同时用一个指针记录位置 (比较tricky,多练几遍)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 <= 200
1 <= T.length <= 200
S
andT
only contain lowercase letters and'#'
characters.
Follow up:
- Can you solve it in
O(N)
time andO(1)
space?
class Solution { public: bool backspaceCompare(string S, string T) { int is = S.length()-1; int it = T.length()-1; int cc = 0; while(is>=0 || it>=0) // using && will omit case of S= "a#" T="" { cc = 0; while(is>=0 && ( S[is]=='#' || cc>0)) { if(S[is] =='#') { cc++; }else{ cc--; } is--; } cc = 0; while(it>=0 && ( T[it]=='#' || cc>0)) { if(T[it] =='#') { cc++; }else{ cc--; } it--; } // now both are valid, do compare now. if(is<0 && it<0) return true; if(is<0 || it<0) return false; if(S[is] != T[it]) return false; is--; it--; } return is<0 && it<0; // not both index are out of range } };
No comments:
Post a Comment