leetcode

Solution to some Leetcode problems written in C++
git clone git://git.dimitrijedobrota.com/leetcode.git
Log | Files | Refs | README | LICENSE

1312.cpp (409B)

      1 class Solution {
      2   public:
      3     int minInsertions(string s) {
      4         int dp[501][501] = {0}, n = s.size();
      5         for (int i = 0; i < n; i++)
      6             for (int j = 0; j < n; j++)
      7                 if (s[i] == s[n - 1 - j])
      8                     dp[i + 1][j + 1] = dp[i][j] + 1;
      9                 else
     10                     dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j]);
     11         return n - dp[n][n];
     12     }
     13 };