Leetcode DP Programs Solution

 Leetcode DP Programs Solution

Longest Palindromic Substring     class Solution { public:     string longestPalindrome(string s) {           int n=s.size();     int dp[n][n];         memset(dp,0,sizeof(dp));     int ix=0,ans=1;     for(int i=0;i<n;i++)         dp[i][i]=1;     for(int i=0;i<n-1;i++)     {         if(s[i]==s[i+1])         {             dp[i][i+1]=1;             ix=i;             ans=2;         }     }     for(int k=3;k<=n;k++)     {         for(int i=0;i<n-k+1;i++)         {           int j=i+k-1;           if(s[i]==s[j]&&dp[i+1][j-1])               {dp[i][j]=1;                        ans=k;               ix=i;           }         }     }     //cout<<ans<<" ";     return s.substr(ix,ans);     } };   Generate Parentheses     class Solution { vector<string>ans;     int n; void solve(string s,int l,int r) {     if(s.size()==2*n)     {         ans.push_back(s);         return;     }     if(l==n)         solve(s+')',l,r+1);     else     {         if(l>r)         {             solve(s+'(',l+1,r);             solve(s+')',l,r+1);         }         else           solve(s+'(',l+1,r);                       } } public:     vector<string> generateParenthesis(int n1) {         n=n1;         string s="";         solve(s,0,0);         return ans;              } };   Longest Valid Parentheses   class Solution { public:     int longestValidParentheses(string s) {         int n=s.size();if(n==0)return 0;         stack<pair<char,int>>st;         st.push({')',-1});         for(int i=0;i<n;i++)         {             if(s[i]=='(')st.push({'(',i});             else             {                 if(st.size()&&st.top().first=='(')st.pop();                 else st.push({')',i});             }         }         int ans=0,prv=n;         while(st.size())         {             ans=max(ans,prv-st.top().second-1);             prv=st.top().second;            // cout<<prv<<" ";             st.pop();         }         return ans;                 } };  Wildcard Matching   #define ll long long int class Solution {     int n,m;     string s1,s2;     public:     bool isMatch(string p, string s) {         n=s.size(),m=p.size();         bool dp[n+1][m+1];         for(int i=0;i<=n;i++)         {             for(int j=0;j<=m;j++)             {                 if(i==0&&j==0)                     dp[i][j]=true;                 else if(i==0)                 {                     if(p[j-1]!='*')                         dp[i][j]=false;                     else                         dp[i][j]=dp[i][j-1]&true;                 }                 else if(j==0)                 {                     if(s[i-1]!='*')                         dp[i][j]=false;                     else                         dp[i][j]=dp[i-1][j]&true;                 }                 else if(s[i-1]=='*')                    dp[i][j]=dp[i-1][j]|dp[i-1][j-1]|dp[i][j-1];                 else if(s[i-1]==p[j-1]||s[i-1]=='?')                     dp[i][j]=dp[i-1][j-1];                 else                     dp[i][j]=false;             }         }         return dp[n][m];                      } };  Maximum Subarray   class Solution { public:     int maxSubArray(vector<int>& nums) {         int ans=nums[0];         for(int i=1;i<nums.size();i++)         {             nums[i]=max(nums[i],nums[i]+nums[i-1]);             ans=max(ans,nums[i]);         }         return ans;     } };