777: Beats 95.06%, Solution with step by step explanation
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n\ni, j = 0, 0\nn, m = len(start), len(end)\n\nWe create two pointers, i a
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n```\ni, j = 0, 0\nn, m = len(start), len(end)\n```\nWe create two pointers, i and j, to iterate through start and end, respectively. We also store the lengths of start and end in n and m.\n\nWe continue while neither i nor j has reached the end of their respective strings.\n\n```\nwhile i < n and j < m:\n```\n\n```\nwhile i < n and start[i] == \'X\':\n    i += 1\nwhile j < m and end[j] == \'X\':\n    j += 1\n```\n\nWe increment the i and j pointers as long as we see the character \'X\' in the respective string. We do this because \'X\' doesn\'t affect our transformation logic.\n\n```\nif (i == n) != (j == m):\n    return False\n```\n\nAfter skipping all \'X\' characters, if one of the pointers has reached the end and the other hasn\'t, the strings cannot be made identical.\n\n```\nif i == n and j == m:\n    return True\n```\n\nIf both pointers have reached the end of their strings simultaneously, they are identical.\n\n```\nif start[i] != end[j]:\n    return False\n```\n\nIf the characters at i and j are different, then the transformation is not possible.\n\n```\nif start[i] == \'R\' and i > j:\n    return False\n```\n\nSince \'R\' can only move right, its position in start should always be to the left (or at the same position) compared to end.\n\n\n```\nif start[i] == \'L\' and i < j:\n    return False\n```\n\nSince \'L\' can only move left, its position in start should always be to the right (or at the same position) compared to end.\n\n```\ni += 1\nj += 1\n```\n\nOnce we\'ve done the checks, we move the pointers to examine the next characters.\n\n```\nwhile i < n and start[i] == \'X\':\n    i += 1\nwhile j < m and end[j] == \'X\':\n    j += 1\n```\n\nAfter exiting the main loop, if there are any \'X\' characters left, we skip them.\n\n```\nreturn i == n and j == m\n```\n\nAt this point, if both i and j have reached the ends of their strings, the transformation is possible; otherwise, it\'s not.\n\n# Complexity\n- Time complexity:\nO(n)\n\n- Space complexity:\nO(1)\n\n# Code\n```\nclass Solution:\n    def canTransform(self, start: str, end: str) -> bool:\n  \n        i, j = 0, 0\n        n, m = len(start), len(end)\n        \n        while i < n and j < m:\n \n            while i < n and start[i] == \'X\':\n                i += 1\n            while j < m and end[j] == \'X\':\n                j += 1\n                \n            if (i == n) != (j == m):\n                return False\n            \n            if i == n and j == m:\n                return True\n            \n            if start[i] != end[j]:\n                return False\n            \n            if start[i] == \'R\' and i > j:\n                return False\n            if start[i] == \'L\' and i < j:\n                return False\n\n            i += 1\n            j += 1\n        \n        while i < n and start[i] == \'X\':\n            i += 1\n        while j < m and end[j] == \'X\':\n            j += 1\n            \n        return i == n and j == m\n\n```
['Two Pointers', 'String', 'Python', 'Python3']