I have solved the below problem with recursion and memoization.
**Given a string s. In one step you can insert any character at any index of the string.
Return the minimum number of steps to make s palindrome.**
Here is my code
class Scratch {
public static int makepalind(String s, int left, int right, int [][]dp) {
if (left > right) return 0;
if (left == right) {
return 0;
}
if (dp[left][right] != -1) return dp[left][right];
if (s.charAt(left) == s.charAt(right)) {
dp[left][right] = makepalind(s, left + 1, right - 1, dp);
return dp[left][right];
}
dp[left][right] = 1 + Math.min(makepalind(s, left + 1, right, dp), makepalind(s, left, right - 1, dp));
return dp[left][right];
}
public static void main(String[] args) {
String s = "leetcode" ;
//String s = "appa" ;
//String s = "leetcode";
int [][]dp = new int[s.length()][s.length()];
for(var arr:dp) {
Arrays.fill(arr,-1);
}
makepalind(s,0,s.length()-1,dp);
// Fill array with 0 and create new array
for(int i = 0; i<s.length(); i++) {
for(int j = 0; j<s.length(); j++) {
if(dp[i][j]==-1) {
dp[i][j] = 0;
}
}
}
for(int i = 0; i<s.length(); i++) {
for(int j = 0; j<s.length(); j++) {
System.out.format("%2d",dp[i][j]);
}
System.out.println();
}
}
}
This code works. But I have some questions on this
Example 1:
Input string "leetcode"
If I print the dp array it comes out as below
0 1 1 2 3 4 5 5
0 0 0 1 2 3 4 4
0 0 0 1 2 3 4 0
0 0 0 0 1 2 3 0
0 0 0 0 0 1 2 0
0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
As can be seen the answer is correct because at zeroth row and col 7, the number is 5
However this array is filled due to recursion in an order which is opposite of how it will get filled if I were to use two for loops beginning from index 0 and going till input string's length.
Example 2:
It gets more obvious if I use madam which is a palindrome string.
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
If however, I were to use the nested for loops that start from 0, the DP array for madam string won't show up like this. I know that this is due to how recursion is unfolding.
I am however, unable to change the recursion and trying to figure out how do I do it so that recursion folds in the opposite way.
this array is filled due to recursion in an order which is opposite of how it will get filled if I were to use two for loops beginning from index 0 and going till input string's length.
The order of the array is as expected. It gives information for all analysed substrings, by using the start index of that substring as Y-coordinate (row index) and the end index (inclusive) of that substring as X-coordinate (column index). With that meaning of row and column index there is no other way to represent the matrix. So in the case of "leetcode" we could represent that dp matrix -- with the labels for row and column indices -- as follows:
| 0 1 2 3 4 5 6 7
--+----------------
0 | 0 1 1 2 3 4 5 5
1 | 0 0 0 1 2 3 4 4
2 | 0 0 0 1 2 3 4 0
3 | 0 0 0 0 1 2 3 0
4 | 0 0 0 0 0 1 2 0
5 | 0 0 0 0 0 0 1 0
6 | 0 0 0 0 0 0 0 0
7 | 0 0 0 0 0 0 0 0
So if for instance we want to know how many insertions are needed to make the substring at indices 2 to 4 a palindrome (where we have the string "etc"), we would look in row 2 and column 4, where we find the value 2. The matrix clearly has to be structured in this order for this lookup to work that way. This is not related to the choice to use recursion, but rather how the matrix is supposed to work for storing and looking up data.
If you would want to have the solution value to appear at the bottom, you'll have to come up with a different encoding strategy. Since we want the solution for the whole string, which starts at index 0 and ends at index 7, you might want to reverse row/column indices in your matrix, so that the matrix appears as:
| 0 1 2 3 4 5 6 7
--+----------------
0 | 0 0 0 0 0 0 0 0
1 | 1 0 0 0 0 0 0 0
2 | 1 0 0 0 0 0 0 0
3 | 2 1 1 0 0 0 0 0
4 | 3 2 2 1 0 0 0 0
5 | 4 3 3 2 1 0 0 0
6 | 5 4 4 3 2 1 0 0
7 | 5 5 0 0 0 0 0 0
To achieve this, just change row/column index when accessing dp:
public static int makepalind(String s, int left, int right, int [][]dp) {
if (left > right) return 0;
if (left == right) {
return 0;
}
if (dp[right][left] != -1) return dp[right][left];
if (s.charAt(left) == s.charAt(right)) {
dp[right][left] = makepalind(s, left + 1, right - 1, dp);
return dp[right][left];
}
dp[right][left] = 1 + Math.min(makepalind(s, left + 1, right, dp), makepalind(s, left, right - 1, dp));
return dp[right][left];
}
There are several other alternative "encodings" you can use for the matrix. For instance, you could use for the row index the right index (as above), but for the column index the difference between the left and right index (so right - left). Then the solution will come up in the bottom-right corner of the matrix.
if I use madam which is a palindrome string: (all zeroes)
The zeroes that you see in the matrix that is produced for input "madam" are mostly put there by the main program after the function has already returned. Only tow of those zeroes are really produced by the recursive algorithm: the one for substring "ada" and the one for "madam". The thing is that as soon as the algorithm finds the palindrome, it returns out of recursion without investigating any other possibilities. It is then the main program that replaces all the other unvisited cells in the matrix.
If you want the algorithm to also look at other substrings (which makes it less optimal), then first perform the two recursive calls you now do at the very end:
// Do this first
dp[right][left] = 1 + Math.min(makepalind(s, left + 1, right, dp), makepalind(s, left, right - 1, dp));
// ...and only then:
if (s.charAt(left) == s.charAt(right)) {
dp[right][left] = makepalind(s, left + 1, right - 1, dp);
}
return dp[right][left];