Python || Top Down DP
Assume board as a grid of mn and store corrdinates of each char in a dictionary.\nuse top down dp and memoize it.\nTime Complexity - O(len(word)m^2*n^2) where m
Assume board as a grid of m*n and store corrdinates of each char in a dictionary.\nuse top down dp and memoize it.\nTime Complexity - O(len(word)*m^2*n^2) where m and n are rows and columns of keyboard\n\n```\nclass Solution:\n    def minimumDistance(self, word: str) -> int:\n        n=len(word)\n        graph={}\n        i,j=0,0\n        for c in ascii_uppercase:\n            graph[c]=(i,j)\n            j=(j+1)%6\n            if j==0:\n                i+=1\n        @cache\n        def dp(idx,fi,fj,si,sj):\n            if idx==n:\n                return 0\n            #use first finger\n            ii,jj=graph[word[idx]]\n            ans=dp(idx+1,ii,jj,si,sj)+(0 if fi==-1 and fj==-1 else abs(ii-fi)+abs(jj-fj))\n            #use second finger\n            ans=min(ans,dp(idx+1,fi,fj,ii,jj)+(0 if si==-1 and sj==-1 else abs(ii-si)+abs(jj-sj)))\n            return ans\n        return dp(0,-1,-1,-1,-1)\n```
['Dynamic Programming', 'Python3']