5-liner & 7-liner two versions O(N^2) clean DP (detailed explanation)


  • 2

    It is natural to solve subsequence related problems with DP because a subsequence of a substring must be a subsequence of the string itself.

    Solution 1:
    We focus on the first s[0] and last char s[n-1] of string s. The longest palindromic subsequence seq of s must be one of the two cases:

    1. s[0] == s[n-1]: seq must include s[0], s[n-1], and therefore, seq without s[0], s[n-1] must be a longest palindromic subsequence of substring s[1:n-2];
    2. s[0] != s[n-1]: seq cannot include both s[0] and s[n-1], so seq is either a palindromic subsequence of substring s[1:n-1] or s[0:n-2].

    Therefore, we have the straightforward DP recursion. Let dp[i][j] = length of longest palindromic subsequence of substring s[i:j] (i<j), then

    • dp[i][j] = s[i]==s[j]? dp[i+1][j-1]+2 : max(dp[i][j-1],dp[i+1][j]).

    Note: we must calculate dp[i][j] with smaller index difference j-i first before larger ones based on the recursion above.

        int longestPalindromeSubseq(string s) {
            int n = s.size(); vector<vector<int>> dp(n, vector<int>(n));
            for(int d = 0; d < n; d++) // d = j-i
                for(int i = 0, j = i+d; j < n; i++,j++)
                    dp[i][j] = d? s[i]==s[j]? dp[i+1][j-1]+2 : max(dp[i][j-1],dp[i+1][j]) : 1;
    
            return dp[0][n-1];
        }
    

    Solution 2:
    We focus only on the last char s[n-1] of string s. Any palindromic subsequence seq of s must be in one of the two categories:

    1. seq does not include s[n-1]: seq must be a palindromic subsequence of substring s[0,n-2];
    2. seq includes s[n-1]: we must have first char of seq s[k] = s[n-1] because of palindrome.Therefore, seq without first char s[k] and last char s[n-1] must be a palindromic subsequence of substring s[k+1,n-2].

    Therefore, we have DP recursion:

    • dp[i][j] = max(dp[i][j-1], k<j? dp[k+1][j-1]+2 : 1),
      where k = the index of first char s[j] in s[i:].
        int longestPalindromeSubseq(string s) {
          int n = s.size(); vector<unordered_map<char,int>> next(n); // next[i][c]: index of first c in s[i:]
          for (int i = n-1; i >= 0; next[i][s[i]] = i--) if (i+1<n) next[i] = next[i+1]; // O(n^2) 
            
          vector<vector<int>> dp(n,vector<int>(n)); // dp[i][j]: result for substring s[i:j]   
          for (int d = 0; d < n; ++d)               // d = j-i: O(n)
            for (int i = 0, j = i+d, k; j < n; ++i,++j) // O(n)
              dp[i][j] = max(dp[i][j-1], (k=next[i][s[j]]) < j? dp[k+1][j-1]+2 : 1);
              
          return dp[0][n-1];
        }
    

  • 0
    L

    Thanks! Very detailed explanation!


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.