[Python3] Backtracking (Not TLE) for beginners only!
When we see constraints 1 <= m, n <= 6 and 1 <= word.length <= 15, it is backtracking! (Not sure if the interviewer will tell you this, but it doesn\'t hurt to 
When we see constraints ```1 <= m, n <= 6``` and ```1 <= word.length <= 15```, it is backtracking! (Not sure if the interviewer will tell you this, but it doesn\'t hurt to ask for some constraints).\n\n**Backtracking** is basically **Brute Force**, where we check **all possibilities** using a **Recursive Function**.\nThe most important parts of backtracking using recursive function are:\n(1) **return** when we reach to the end and no more states can be generated.\n(2) **restore the state** after calling the recursive function.\ni.e.,\n```\ndef backtrack(state):\n(1) if there are no more states that can be generated from the current state, return.\n\nFor loop\n    (2) change the current state to its neighboring state\n    (3) backtrack(state)\n    (4) restore the state (backtrack)\n```\n\nFor this problem, \n(1) We will **Brute Force all possibilities**, which means we will try to start at each cell in the ```grid``` to construct the word (or say, compare the cell with word[k], where 0<=k<len(word)) using Backtracking (a Recursive Function).\n\n(2) Backtracking:\n - if the current cell is the same as word[k], we keep searching.\n - if k is already at the last position in the word, we find a solution, so return True.\n\n    Now think about the state as the visited cells since we cannot reuse a cell.\n\n - for the four possible directions (up, down, left, right):\n (1) check if the new cell is valid (inside the grid)\n (2) add the new cell (x,y) to our visited list.\n (3) do Backtracking using this newly visited list.\n (4) remove the last added cell from the visited list. (This step is the reason why it is called backtrack)\n\n(3) return False if we couldn\'t reconstruct the word.\n\n```python\nclass Solution:\n    def exist(self, board: List[List[str]], word: str) -> bool:\n        \n        directions = [[0,1],[1,0],[0,-1],[-1,0]]\n        m,n = len(board),len(board[0])\n        \n        def backtrack(i,j,k,visited):\n            if board[i][j] == word[k]:\n                if k==len(word)-1:\n                    return True\n                \n                for xn,yn in directions:\n                    x,y = i+xn,j+yn\n                    if 0<=x<m and 0<=y<n and (x,y) not in visited:\n                        visited.add((x,y))                      # Change the state\n                        if backtrack(x,y,k+1,visited)==True:    # Recursive call\n                            return True\n                        visited.remove((x,y))                   # Restore the state\n            return False\n        \n        # start from each cell in the grid.\n        for i in range(m):\n            for j in range(n):\n                if backtrack(i,j,0,{(i,j)}):\n                    return True\n        return False\n```\n\nThis may sometimes get TLE!\n\n**Follow up:** Could you use search pruning to make your solution faster with a larger board?\n\nWe need to prune the search further! Learned from [Here](https://leetcode.com/problems/word-search/discuss/2843501/PythonC%2B%2B-faster-than-99-DFS-(explained)) and also [Minamikaze392](https://leetcode.com/Minamikaze392/)\'s comments.\n\n**(1)** If there are fewer elements in the board than the word, return directly! (not helping much, but it is still an answer)\n**(2)** If there are fewer characters in the board than the word, return directly! (no TLE anymore)\n\nIf you got TLE, you might have seen this testing case:\n```\n[["A","A","A","A","A","A"],\n["A","A","A","A","A","A"],\n["A","A","A","A","A","A"],\n["A","A","A","A","A","A"],\n["A","A","A","A","A","B"],\n["A","A","A","A","B","A"]]\n\n"AAAAAAAAAAAAABB"\n```\n\nIf we start to search from the right with \'A\', there are too many branches! So if we reverse the word and start the search from the right with \'B\', it will be more efficient!\n\nAs commented by [Minamikaze392](https://leetcode.com/Minamikaze392/) what if the testing case looks like this (it is not currently in LeetCode):\n```\n[["A","A","A","A","A","A"],\n["A","A","A","A","A","A"],\n["A","A","A","A","A","A"],\n["A","A","A","A","A","A"],\n["A","A","A","A","A","B"],\n["A","A","A","A","B","A"]]\n\n"AAAAAAAAAAAAABBA"\n```\n\n**(3)** A general pruning approach here is that we start the search from the right if at any point the duplicates on the right are less than the left. (see code below)\n\n```python\nclass Solution:\n    def exist(self, board: List[List[str]], word: str) -> bool:\n        \n        directions = [[0,1],[1,0],[0,-1],[-1,0]]\n        m,n = len(board),len(board[0])\n        \n        # (1) fewer elements in the board than the word.\n        if m*n<len(word): return False\n        \n        # (2) fewer characters in the board than the word.\n        countB = Counter()\n        for i in range(m):\n            for j in range(n):\n                countB[board[i][j]] += 1\n        countW = Counter(word)\n        for key in countW.keys():\n            if countW[key] - countB[key] > 0:\n                return False\n        \n        # (3) Inverse word if it\'s better\n        # If we find the right duplicates are less than the left duplicates, reverse the word.\n        left,right = 1,len(word)-2\n        leftDup = rightDup = 1\n        while left<right:\n            if word[left]==word[left-1]:\n                leftDup += 1\n            if word[right]==word[right+1]:\n                rightDup += 1\n                \n            if rightDup<leftDup:\n                word = word[::-1]\n                break\n                \n            if word[left]!=word[left-1]:\n                leftDup = 1\n            if word[right]!=word[right+1]:\n                rightDup = 1\n            left += 1\n            right -= 1\n            \n        def backtrack(i,j,k,visited):\n            if board[i][j] == word[k]:\n                if k==len(word)-1:\n                    return True\n                for xn,yn in directions:\n                    x,y = i+xn,j+yn\n                    if 0<=x<m and 0<=y<n and (x,y) not in visited:\n                        if backtrack(x,y,k+1,visited.union({(x,y)}))==True:\n                            return True\n            return False\n        \n        for i, j in product(range(m), range(n)):\n            if backtrack(i,j,0,{(i,j)}):\n                return True\n        return False\n```\n\n**Upvote** if you like this post.\n\n**Connect with me on [LinkedIn](https://www.linkedin.com/in/meida-chen-938a265b/)** if you\'d like to discuss other related topics\n\n\uD83C\uDF1F If you are interested in **Machine Learning** || **Deep Learning** || **Computer Vision** || **Computer Graphics** related projects and topics, check out my **[YouTube Channel](https://www.youtube.com/@meidachen8489)**! Subscribe for regular updates and be part of our growing community.
[]