Given two strings s and t, return true 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 = "b " Output: false Explanation: s becomes "c " while t becomes "b ".
Constraints:
1 <= s.length, t.length <= 200s and t only contain lowercase letters and '#' characters.Follow up: Can you solve it in O(n) time and O(1) space?
program main
implicit none
integer :: i, j, n
character(len=200) :: s, t
logical :: result
! Example 1: ab#c , ad#c
s = 'ab#c '
t = 'ad#c '
result = is_equal_after_backspace(s, t)
print '(L1)', result
! Example 2: ab## , c#d#
s = 'ab## '
t = 'c#d# '
result = is_equal_after_backspace(s, t)
print '(L1)', result
! Example 3: a#c , b
s = 'a#c '
t = 'b'
result = is_equal_after_backspace(s, t)
print '(L1)', result
contains
function is_equal_after_backspace(s, t) result(res)
implicit none
character(len=*), intent(in) :: s, t
logical :: res
integer :: i, j
res = .false.
if (len(s) /= len(t)) return
i = 1
j = 1
do while (i <= len(s))
if (s(i:i) == '#') then
i = i + 1
else if (t(j:j) == '#') then
j = j + 1
else if (s(i:i) /= t(j:j)) then
return
end if
i = i + 1
j = j + 1
end do
res = .true.
end function is_equal_after_backspace
end program mainF F F
! This is a full Fortran script with a valid main entry point that solves the problem.
module Solution
implicit none
contains
logical function backspaceCompare(s, t) result(equal)
! Arguments
character(len=*), intent(in) :: s, t
! Variables
integer :: i, j, k
! Initialize variables
i = 1
j = 1
k = 1
! Loop through the strings
do while (i <= len(s) .and. j <= len(t))
! If the current character is a backspace
if (s(i:i) == '#') then
! If there are no more characters to backspace
if (k == 1) then
! Return false
equal = .false.
return
end if
! Decrement the number of characters
k = k - 1
else
! If the current character is not a backspace
if (s(i:i) /= t(j:j)) then
! If the characters do not match
equal = .false.
return
end if
! Increment the number of characters
k = k + 1
end if
! Increment the indices
i = i + 1
j = j + 1
end do
! If the strings are not the same length
if (i <= len(s) .or. j <= len(t)) then
! Return false
equal = .false.
return
end if
! If the strings are the same length
equal = .true.
end function backspaceCompare
end module Solution
program Main
! Arguments
character(len=200) :: s, t
! Variables
logical :: equal
! Read the input strings
read (*, *) s
read (*, *) t
! Call the backspaceCompare function
equal = backspaceCompare(s, t)
! Print the result
if (equal) then
write (*, *) "True"
else
write (*, *) "False"
end if
end program Main
temp.f95:77:12:
77 | equal = backspaceCompare(s, t)
| 1
Error: Cannot convert REAL(4) to LOGICAL(4) at (1)
def backspaceCompare(s: str, t: str) -> bool:
i, j = len(s) - 1, len(t) - 1
while True:
back = 0
while i >= 0 and (back > 0 or s[i] == '#'):
back = back + 1 if s[i] == '#' else back - 1
i -= 1
back = 0
while j >= 0 and (back > 0 or t[j] == '#'):
back = back + 1 if t[j] == '#' else back - 1
j -= 1
if i >= 0 and j >= 0 and s[i] == t[j]:
i, j = i -1, j - 1
else:
return i == -1 and j == -1
The algorithm implements a two-pointer approach to compare the characters in the given strings s and t. We initialize two pointers i and j at the end of the respective strings. We use two nested loops to iterate through the characters from right to left, considering the backspace characters.
In both loops, we maintain a backspace counter. If we encounter a backspace character, we increment the counter. If we encounter a non-backspace character while the counter is greater than 0, we decrement the counter and continue. This effectively simulates the deletion of characters due to backspace.
We then compare the characters at positions i and j. If they are equal, we decrement both pointers. If they are not equal, we break the loop and check if both pointers are equal to -1, indicating that both strings are equal after considering backspaces. If both pointers are equal to -1, we return true; otherwise, we return false.
This algorithm has a time complexity of O(n), where n is the length of the input strings, and a space complexity of O(1) as we do not use any additional data structures.
bool backspaceCompare(string s, string t) {
int i = s.length() - 1, j = t.length() - 1;
while (true) {
int back;
for (back = 0; i >= 0 && (back > 0 || s[i] == '#'); --i)
back += s[i] == '#' ? 1 : -1;
for (back = 0; j >= 0 && (back > 0 || t[j] == '#'); --j)
back += t[j] == '#' ? 1 : -1;
if (i >= 0 && j >= 0 && s[i] == t[j])
i--, j--;
else
return i == -1 && j == -1;
}
}
The algorithm implements a two-pointer approach to compare the characters in the given strings s and t. We initialize two pointers i and j at the end of the respective strings. We use two nested loops to iterate through the characters from right to left, considering the backspace characters.
In both loops, we maintain a backspace counter. If we encounter a backspace character, we increment the counter. If we encounter a non-backspace character while the counter is greater than 0, we decrement the counter and continue. This effectively simulates the deletion of characters due to backspace.
We then compare the characters at positions i and j. If they are equal, we decrement both pointers. If they are not equal, we break the loop and check if both pointers are equal to -1, indicating that both strings are equal after considering backspaces. If both pointers are equal to -1, we return true; otherwise, we return false.
This algorithm has a time complexity of O(n), where n is the length of the input strings, and a space complexity of O(1) as we do not use any additional data structures.