source: https://leetcode.com/problems/minimum-insertion-steps-to-make-a-string-palindrome/description/
Minimum Insertion Steps to Make a String Palindrome
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.
A Palindrome String is one that reads the same backward as well as forward.
Example 1:
Input: s = “zzazz”
Output: 0
Explanation: The string “zzazz” is already palindrome we do not need any insertions.
Example 2:
Input: s = “mbadm”
Output: 2
Explanation: String can be “mbdadbm” or “mdbabdm”.
Example 3:
Input: s = “leetcode”
Output: 5
Explanation: Inserting 5 characters the string becomes “leetcodocteel”.
Constraints:
- 1 <= s.length <= 500
- s consists of lowercase English letters.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
class Solution { public int minInsertions(String s) { int[][] memo = new int[s.length()+1][s.length()+1]; for(int[] m: memo){ Arrays.fill(m, -1); } return dfs(s, 0, s.length()-1, memo); } public int dfs(String s, int l, int r, int[][] memo){ if(l>=r) return 0; if(memo[l][r]!=-1) return memo[l][r]; int min = Integer.MAX_VALUE; //if both the characters are equal //move left and right pointers char cl = s.charAt(l); char cr = s.charAt(r); if(cl==cr){ min = Math.min(min, dfs(s, l+1, r-1, memo)); } else { //you can either add a character on the left side int left = 1+dfs(s, l, r-1, memo); //or you can add a character on the right side int right = 1+dfs(s, l+1, r, memo); min = Math.min(min, Math.min(left, right)); } memo[l][r] = min; return min; } } |