4 Solutions: TLE -> O(n) Space Optimised - Python/Java
Intuition\n\nIn spite of the downvotes I actually thought this was a pretty good question, even though only the O(n) passes. \n\nI\'ve heavily commented the cod
> # Intuition\n\nIn spite of the downvotes I actually thought this was a pretty good question, even though only the O(n) passes. \n\nI\'ve heavily commented the code with explanations, and provided the brute force alternatives that don\'t pass for people like me who find those helpful:\n\n---\n\n\n> # DFS (TLE)\n\n```python []\n#TLE - DFS\nclass Solution:\n    def canTransform(self, start: str, end: str) -> bool:\n        #after we\'ve altered the string at some index\n        #we need to start i from the beginning, so for the dfs\n        #a for loop is needed\n        def dfs(curr):\n            #if the current string we\'re on ever hits the end\n            if curr == end:\n                #pass true back up the call stack\n                return True\n\n            #attempt to change each character in the string\n            for i in range(len(curr)):\n                #if the search isn\'t out of bounds\n                if i+1<len(curr):\n                    curr_string = curr[i]+curr[i+1]\n                    #then try to make each i "XL" or "XR" if possible\n                    if curr_string == "XL" and dfs(curr[:i]+"LX"+curr[i+2:]):\n                        return True\n                    elif curr_string == "RX" and dfs(curr[:i]+"XR"+curr[i+2:]):\n                        return True\n            return False\n        return dfs(start)\n```\n```Java []\n//Java - TLE - DFS\nclass Solution{\n    private String end;\n    public Solution(){};\n\n    public boolean canTransform(String start, String end){\n        this.end = end;\n        return dfs(start);\n    }\n\n    private boolean dfs(String curr){\n        if (curr.equals(end)){\n            return true;\n        }\n        for (int i = 0; i < curr.length();i++){\n            if (i+1<curr.length()){\n                String curr_string = (""+curr.charAt(i))+(""+curr.charAt(i+1));\n                String lx_string = curr.substring(0, i)+"LX"+curr.substring(i+2, curr.length());\n                String rx_string = curr.substring(0, i)+"XR"+curr.substring(i+2, curr.length());\n                if (curr_string.equals("XL") && dfs(lx_string)){\n                    return true;\n                }else if(curr_string.equals("RX") && dfs(rx_string)){\n                    return true;\n                }\n            }\n        }\n        return false;\n    }\n}\n```\n\n---\n\n> # DFS + Memoisation (TLE)\n\n```python []\n#TLE - DFS + Memo\nclass Solution:\n    def canTransform(self, start: str, end: str) -> bool:\n        #exact same concept as the DFS solution, except we memoise\n        #the strings, although this still gives TLE\n        map = {}\n        def dfs(curr):\n            if curr == end:\n                return True\n            elif curr in map:\n                return map[curr]\n            \n            map[curr] = False\n            for i in range(len(curr)):\n                if i+1<len(curr):\n                    curr_string = curr[i]+curr[i+1]\n                    if curr_string == "XL" and dfs(curr[:i]+"LX"+curr[i+2:]):\n                        return True\n                    elif curr_string == "RX" and dfs(curr[:i]+"XR"+curr[i+2:]):\n                        return True\n            return map[curr]\n        return dfs(start)\n```\n```Java []\n//Java - TLE - DFS + Memo\nclass Solution{\n    private String end;\n    private Map<String,Boolean> map;\n    public Solution(){\n        this.map = new HashMap<>();\n    };\n    \n    public boolean canTransform(String start, String end){\n        this.end = end;\n        return dfs(start);\n    }\n\n    private boolean dfs(String curr){\n        if (curr.equals(end)){\n            return true;\n        }else if (map.containsKey(curr)){\n            return map.get(curr);\n        }\n        map.put(curr, false);\n        for (int i = 0; i < curr.length();i++){\n            if (i+1<curr.length()){\n                String currString = (""+curr.charAt(i))+(""+curr.charAt(i+1));\n                String lx_string = curr.substring(0, i)+"LX"+curr.substring(i+2, curr.length());\n                String rx_string = curr.substring(0, i)+"XR"+curr.substring(i+2, curr.length());\n                if (currString.equals("XL")&& dfs(lx_string)){\n                    return true;\n                }else if (currString.equals("RX")&& dfs(rx_string)){\n                    return true;\n                }\n            }\n        }\n        return map.get(curr);\n    }\n}\n```\n\n---\n\n> # BFS\n\n```python []\n#TLE BFS + Memo\nclass Solution:\n    def canTransform(self, start: str, end: str) -> bool:\n        #Sadly BFS also too slow, we remember the strings using \n        #a hashset\n        q = [start]\n        seen = set()\n        while q:\n            curr = q.pop()\n            if curr == end:\n                return True\n            elif curr in seen:\n                continue\n            #for each string, try changing the characters\n            #and adding it to the queue if it\'s valid\n            for i in range(len(curr)):\n                if i+1<len(curr):\n                    curr_string = curr[i]+curr[i+1]\n                    if curr_string == "XL":\n                        q.append(curr[:i]+"LX"+curr[i+2:])\n                        #add the string to seen so we don\'t re-visit it\n                        seen.add(curr)\n                    elif curr_string == "RX":\n                        q.append(curr[:i]+"XR"+curr[i+2:])\n                        seen.add(curr)\n        return False\n```\n```Java []\n//Java - BFS + Memo\nclass Solution {\n    public Solution(){};\n    public boolean canTransform(String start, String end) {\n        Queue<String> q = new LinkedList<>();\n        Set<String> seen = new HashSet<>();\n\n        q.add(start);\n        seen.add(start);\n\n        while (!q.isEmpty()) {\n            String curr = q.poll();\n            \n            if (curr.equals(end)) {\n                return true; \n            }\n\n            for (int i = 0; i < curr.length(); i++) {\n                if (i + 1 < curr.length()) {\n                    String curr_string = curr.substring(i, i + 2);\n                    if (curr_string.equals("XL")) {\n                        String next = curr.substring(0, i) + "LX" + curr.substring(i + 2);\n                        if (!seen.contains(next)) {\n                            q.add(next);\n                            seen.add(next);\n                        }\n                    } else if (curr_string.equals("RX")) {\n                        String next = curr.substring(0, i) + "XR" + curr.substring(i + 2);\n                        if (!seen.contains(next)) {\n                            q.add(next);\n                            seen.add(next);\n                        }\n                    }\n                }\n            }\n        }\n        return false;\n    }\n}\n```\n\n---\n\n> # O(n)\n\nCredit `@HigherBro`\n```python []\n#O(n)\nclass Solution:\n    def canTransform(self, start: str, end: str) -> bool:\n        #to get the O(n) solution for this problem, you have to\n        #use the constraints of the question\n\n        #often with these true/false type questions, or optimising\n        #problems with vague statements, we need to use our environment\n        #or things we already know about the expected input/output\n\n        #since XL can only be replaced with LX, and RX can only be\n        #replaced with XR, we know that if we ever encounter a scenario\n        #where L is next to R or R is next to L e.g "LR" or "RL" it\'ll\n        #be impossible for us to ever transform one to the other\n        #meaning, if we simply strip the start and end strings of all X\'s\n        #start should == end\n\n        #why? the shuffling of start to end should ONLY be influenced by X delimiters\n        #if the string is valid. meaning if when we remove all X\'s, and the strings aren\'t the same\n        #we know some other operation involving the crossing of R\'s and L\'s occurred (with no X\'s in between),\n        #or the count of characters in start and end aren\'t the same\n        #therefore no matter how many times we move XL or RX, getting the end is impossible\n\n        #so let\'s remove the X\'s and if they\'re not the same we immediately return False\n        if start.replace("X","") != end.replace("X",""):\n            return False\n\n        #if they are, we know it may be possible to swap some characters\n        #and get the end string\n        #PROVIDED THAT all indexes of occurances of L in start, are less than L\n        #in end, and all indexes of occurances of R in start are greater than R in end\n        #if you notice, when we\'re swapping XL to LX, L is essentially moving to the left\n        #likewise with R, R is moving to the right. \n        #meaning so long as we DON\'T encounter an occurance of L in end that exceeds\n        #it\'s corresponding index in start, it\'s possible to swap these characters\n        #and ultimately form the string end. Notice we just need to return if it\'s possible, \n        #and not the number of times, so this will work\n\n        #find the indexes of l\'s and r\'s in both strings\n        l_start, l_end, r_start, r_end = [],[],[],[]\n        for i in range(len(start)):\n            if start[i] == "L":\n                l_start.append(i)\n            elif start[i] == "R":\n                r_start.append(i)\n            if end[i] == "L":\n                l_end.append(i)\n            elif end[i] == "R":\n                r_end.append(i)\n\n        #go through the l\'s to verify the indexes:\n        for i in range(len(l_start)):\n            if l_start[i]<l_end[i]:\n                return False\n            \n        #do the same for the ends\n        for i in range(len(r_start)):\n            if r_start[i]>r_end[i]:\n                return False\n        \n        #if we never disprove the string, return true\n        return True\n```\n```Java []\n//Java - O(n)\nclass Solution {\n    public Solution() {};\n\n    public boolean canTransform(String start, String end) {\n        if (!start.replace("X", "").equals(end.replace("X", ""))) {\n            return false;\n        }\n\n        List<Integer> l_start = new ArrayList<Integer>();\n        List<Integer> l_end = new ArrayList<Integer>();\n        List<Integer> r_start = new ArrayList<Integer>();\n        List<Integer> r_end = new ArrayList<Integer>();\n\n        for (int i = 0; i < start.length(); i++) {\n            if (start.charAt(i) == \'L\') {\n                l_start.add(i);\n            } else if (start.charAt(i) == \'R\') {\n                r_start.add(i);\n            }\n            if (end.charAt(i) == \'L\') {\n                l_end.add(i);\n            } else if (end.charAt(i) == \'R\') {\n                r_end.add(i);\n            }\n        }\n\n        for (int i = 0; i < l_start.size(); i++) {\n            if (l_start.get(i) < l_end.get(i)) {\n                return false;\n            }\n        }\n\n        for (int i = 0; i < r_start.size(); i++) {\n            if (r_start.get(i) > r_end.get(i)) {\n                return false;\n            }\n        }\n        return true;\n    }\n}\n\n```\n\n---\n\n> # O(n) Space Optimised\nCredit `@Samuel_Ji`\n```python []\n#O(n) less space\nclass Solution:\n    def canTransform(self, start: str, end: str) -> bool:\n        #we can optimise the O(n) to use less space by using two pointers\n        \n        #we still need to ensure the strings possess the same characters \n        #this in essence serves two purposes\n        # 1. ensure the strings possess the same count of characters for each distinct character\n        # 2. ensures if they have the same characters, that they\'re in the same order\n        #    to avoid situations like "LR" and "RL"    \n        if start.replace("X","") != end.replace("X",""):\n            #we can have cases such as:\n            #start = "RXR"\n            #end = "XXR"\n            #here start actually has more R\'s than end, so it\'s impossible to make it into XXR\n            return False\n\n        #p1 and p2 begin at the start of both strings\n        p1,p2 = 0,0\n\n        #we stay in the loop while at least 1 pointer is less\n        #than it\'s respective string\n        while p1 < len(start) and p2 < len(end):\n            #based on the previous O(n) solution, we know the X\'s\n            #are largely irrelevant for this problem, so lets just increment the pointers\n            #and skip them. We still need their presence in the strings however, in order\n            #to track indexes for p1 and p2\n            while p1 < len(start) and start[p1] == "X":\n                p1+=1 \n            while p2 < len(end) and end[p2] == "X":\n                p2+=1 \n            \n            #if both have hit the end of the string at this point\n            if p1 == len(start) and p2 == len(end):\n                #then it\'s transformable\n                return True\n            #if one has, and one hasn\'t\n            elif p1 == len(start) or p2 == len(end):\n                #we know it\'s not transformable\n                return False\n            else:\n                #if we\'ve made it this far the characters are valid\n                #so we just now need to ensure the start index exceeds the end in the case of L\n                #and the start preceeds end in the case of R\n                if (start[p1] == "L" and p1 < p2) or (start[p1] == "R" and p1>p2):\n                    return False\n            #if none of the above are triggered move on to the next character\n            p1 +=1\n            p2 +=1\n        #if we make it out\n        return True\n```\n```Java []\n//Java - O(n) less space\nclass Solution {\n    public Solution() {}\n    public boolean canTransform(String start, String end) {\n        if (!start.replace("X", "").equals(end.replace("X", ""))) {\n            return false;\n        }\n\n        int p1 = 0;\n        int p2 = 0;\n\n        while (p1 < start.length() && p2 < end.length()) {\n            while (p1 < start.length() && start.charAt(p1) == \'X\') {\n                p1 += 1;\n            }\n\n            while (p2 < end.length() && end.charAt(p2) == \'X\') {\n                p2 += 1;\n            }\n\n            if (p1 == start.length() && p2 == end.length()) {\n                return true;\n            } else if (p1 == start.length() || p2 == end.length()) {\n                return false;\n            } else {\n                if ((start.charAt(p1) == \'L\' && p1 < p2) || (start.charAt(p1) == \'R\' && p1 > p2)) {\n                    return false;\n                }\n            }\n            p1 += 1;\n            p2 += 1;\n        }\n        return true;\n    }\n}\n```\n\n\n
['Two Pointers', 'Depth-First Search', 'Breadth-First Search', 'Python', 'Java', 'Python3']