[JAVA] Just another Top Down Recursion
Just like my other posts, this solution would most likely be on the lines of how one can approach the solution to a problem like this. It won\'t be the most opt
Just like my other posts, this solution would most likely be on the lines of how one can approach the solution to a problem like this. It won\'t be the most optimal one. \n\nSo, first let\'s define what the question wants us to do: **Given the string word, return the minimum total distance to type such string using only two fingers.**. Now, let us write it in a function form:\n\nLet\'s define a function fn() which does exactly this. *Function fn() returns the minimum total distance to type a string s with 2 fingers*. What all would be the variables? What all is needed for this function to work? There are 3 things required to get a solution to our function fn:-\n\n1. At which character in the word we are.\n2. Where is our first finger located.\n3. Where is our second finger located.\n\nDo we need to move both fingers at the same time (that is, should our state function be defined by the movement of both fingers in one state)? Or can we work with just moving one finger at a time (that is, we can define the state with just moving one finger at a time)? \n\nSince it is not required that the movement from character i -> j and then j -> k  (for any string s =  argt.....ijkyt..) be in any way dependent or related to which finger we move, we can go by the second approach.\n\nThus, our final function is:-\n\n```\nfn(s, i, a, b): total minimum distance to type string s (ending at index i) with first finger at character a and the second finger at character b.\n```\n\nNow that we have declared our function, let\'s define it. How will this function be structured?\n\nFrom fn(s, i, a, b), we can go to fn(s, i-1, s[i], b) (that is, move the first finger from character a to character s[i]) and add the corresponding cost of moving the first finget from character a -> character s[i], OR we can go to fn(s, i-1, a, s[i]) (that is, we moved the second finder, from character b to character s[i]) and add the corresponding cost of moving the second finger from b -> s[i]. That is:\n\n```\nfn(s,i,a,b) = min(dist(a, s[i]) + fn(s, i-1, s[i], b), dist(b, s[i]) + fn(s, i-1, a, s[i])).\n```\n\nOkay. So we have figured out most of the question and it didn\'t seem that hard. The one thing that took time for me to implement properly (because I am out of practice) was to get the cost of going from any character i -> j. That is it took me a little time to implement dist(i,j). How I went about it:\n\nWe can see that each row corresponds to 6 characters. If we index each character starting at 0, we can get at which row and col they are by using the divide and modulo operations respectively. Let\'s take a few examples to understand it properly:\nA => (i = 0) => (i/6 = 0 [implying 0th row]) => (i%6 = 0 [implying 0th column])\nU => (i = 20) => (i/6 = 3 [implying 3rd row]) => (i%6 = 2 [implying 2nd col])\nQ => (i = 16) => [2(i/6), 4[i%6]].\nF => (i = 5) => [0,5]\n\nThus, we can now map indexes with their row and col. How to map their cost? It is also easy. Let\'s say we have to move from F(0,5) -> U(3,2). We know that we can move along the lines of x and y axis only. That is, we have to go from x=0 to x=3 AND y=5 to y=3 (given that we treat x as horizontal axis and y as vertical axis). Thus, total movement would be movementAlongX + movementAlongY. That is, \n\n```\nprivate int dist(i,j) {\n\tint x1 = i/6, y1 = i%6, x2 = j/6, y2 = j%6;\n\treturn Math.abs(x1-x2) + Math.abs(y1-y2);\n}\n```\n\nNow we have everything that we need. Let\'s put it all into our final solution:-\n\n```\n\tint[][] map; //We create the distance map at the begining\n    \n    public int minimumDistance(String word) {\n        initMap();\n\t\t//I started from null characters. A null character tells that we have not used that finger (to press any character) till now. Since I did it, thus I need to be careful to handle it in my implementation.\n        return fn(word, word.length()-1, \'\\0\', \'\\0\');\n    }\n    \n    private void initMap() {\n        map = new int[26][26];\n        for(int i = 0; i < 26; i++) {\n            for(int j = 0; j < 26; j++) {\n                if(i == j) {\n                    map[i][j] = 0; //No cost in moving from i to i OR j to j\n                }\n                else {\n                    map[i][j] = dist(i, j);\n                }\n            }\n        }\n    }\n    \n    private int dist(int i, int j) {\n        int x1 = i/6, y1 = i%6, x2 = j/6, y2 = j%6;\n        return Math.abs(x1 - x2) + Math.abs(y1 - y2);\n    }\n    \n    private int fn(String word, int i, char a, char b) {\n        if(i < 0) {\n            return 0;\n        }\n        char c = word.charAt(i);\n        int movFirst = Integer.MAX_VALUE, movSec = Integer.MAX_VALUE;\n\t\t//Either move the first finger from a -> c. Also handling the case if we have not used the first finger for any character till now.\n        if(a != \'\\0\') {\n            movFirst = \n                map[a - \'A\'][c - \'A\'] + fn(word, i-1, c, b);\n        }\n        else {\n            movFirst = fn(word, i-1, c, b);\n        }\n\t\t//Or move the second finger from b -> c. Similarly handle the null character case\n        if(b != \'\\0\') {\n            movSec = \n                map[b - \'A\'][c - \'A\'] + fn(word, i-1, a, c);\n        }\n        else {\n            movSec = fn(word, i-1, a, c);\n        }\n        int ans = Math.min(movFirst, movSec);\n        return ans;\n    }\n```\n\nTime complexity: For building the map, we would need O(26\\*26) time. For executing one state, we would need O(1) time. How many states (how many brances possible for this recursion)? Well at every state, we have 2 options (either use the first finger, or the second finger). Thus, we can have O(2^m) states possible (m: length of word). Thus, final time complexity for unoptimized solution: O(26\\*26 + 2^m).\n\nHow can we optimize? We can memoize it based on the fact that once we land on any state, there are three params that define that state uniquely: the character that we are in (defined by index i), the position of the first finger (defined by a) and the position of the second finger (defined by b). Note that a and b could be represented as integer indexes for our dp array. Also, we might need to consider the null characters that we are using in our approach. Thus, the final memoized solution:\n\n```\nint[][] map;\n    Integer[][][] dp;\n    \n    public int minimumDistance(String word) {\n        initMap();\n        dp = new Integer[word.length()+1][27][27];\n        return fn(word, word.length()-1, \'\\0\', \'\\0\');\n    }\n    \n    private void initMap() {\n        map = new int[26][26];\n        for(int i = 0; i < 26; i++) {\n            for(int j = 0; j < 26; j++) {\n                if(i == j) {\n                    map[i][j] = 0;\n                }\n                else {\n                    map[i][j] = dist(i, j);\n                }\n            }\n        }\n    }\n    \n    private int dist(int i, int j) {\n        int x1 = i/6, y1 = i%6, x2 = j/6, y2 = j%6;\n        return Math.abs(x1 - x2) + Math.abs(y1 - y2);\n    }\n    \n    private int fn(String word, int i, char a, char b) {\n        if(i < 0) {\n            return 0;\n        }\n        int ka = (a != \'\\0\') ? (a - \'A\'): 26;\n        int kb = (b != \'\\0\') ? (b - \'A\'): 26;\n        if(dp[i][ka][kb] != null) {\n            return dp[i][ka][kb];\n        }\n        char c = word.charAt(i);\n        int movFirst = Integer.MAX_VALUE, movSec = Integer.MAX_VALUE;\n        if(a != \'\\0\') {\n            movFirst = \n                map[a - \'A\'][c - \'A\'] + fn(word, i-1, c, b);\n        }\n        else {\n            movFirst = fn(word, i-1, c, b);\n        }\n        if(b != \'\\0\') {\n            movSec = \n                map[b - \'A\'][c - \'A\'] + fn(word, i-1, a, c);\n        }\n        else {\n            movSec = fn(word, i-1, a, c);\n        }\n        int ans = Math.min(movFirst, movSec);\n        dp[i][ka][kb] = ans;\n        return ans;\n    }\n```\n\nFinal Time complexity: Time to execute function fn: O(1). Total number of times fn would be called for different states = total different states possible = 27\\*27\\*m. Thus, the final time complexity would be O(26\\*26 + 27\\*27\\*m) (m : length of string).\nFinal space complexity: O(26\\*26) (for the dist map) + O(27 \\* 27 \\* m) (for the dp 3D array).
[]