Given two strings
Note that after backspacing an empty text, the text will continue empty.
Example 1:
Example 2:
Example 3:
Example 4:
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?
Code
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 |
class Solution { public boolean backspaceCompare(String S, String T) { int i = S.length() - 1, j = T.length() - 1; int sS = 0, sT = 0; while (i >= 0 || j >= 0) { while (i >= 0) { if (S.charAt(i) == '#') { sS++; i--; } else if (sS > 0) { sS--; i--; } else break; } while (j >= 0) { if (T.charAt(j) == '#') { sT++; j--; } else if (sT > 0) { sT--; j--; } else break; } if (i >= 0 && j >= 0 && S.charAt(i) != T.charAt(j)) return false; if ((i >= 0) != (j >= 0)) return false; i--; j--; } return true; } } |
We encourage you to write a comment if you have a better solution or having any doubt on the above topic.