Q60 Minimum Insertion Steps to Make a String Palindrome - LeetCode 1316
Sun Apr 02 2023 07:13:07 GMT+0000 (Coordinated Universal Time)
Saved by
@Ayush_dabas07
class Solution {
public int minInsertions(String s) {
/* Q60 of dp playlist , find longest pallindromic subsequnce
then minimum insertion to make strings pallindromic becomes
str.length() - LPS;
*/
//code of LPS
int n = s.length();
int[][] dp = new int[n][n];
for(int gap = 0 ; gap < n ; gap++){
for(int i = 0 , j = gap ; j < n ; j++,i++){
if(gap == 0)
dp[i][j] = 1;
else if(gap == 1)
dp[i][j] = s.charAt(i)==s.charAt(j) ? 2 :1;
else{
char ch1 = s.charAt(i) , ch2 = s.charAt(j);
if(ch1 == ch2)
dp[i][j] = dp[i+1][j-1] + 2;
else
dp[i][j] = Math.max(dp[i][j-1] , dp[i+1][j]);
}
}
}
//minimum insertions becomes
return s.length() - dp[0][n-1];
}
}
content_copyCOPY
https://leetcode.com/problems/minimum-insertion-steps-to-make-a-string-palindrome/
Comments