Valid Palindrome III Solutions in C++

/// Source : https://leetcode.com/problems/valid-palindrome-iii/
/// Author : liuyubobobo
/// Time   : 2019-10-06

#include <iostream>
#include <vector>

using namespace std;


/// Memory Search
/// Time Complexity: O(|s|^2)
/// Space Complexity: O(|s|^2)
class Solution {
public:
    bool isValidPalindrome(string s, int k) {

        vector<vector<int>> dp(s.size(), vector<int>(s.size(), -1));
        return dfs(s, 0, s.size() - 1, dp) <= k;
    }

private:
    int dfs(const string& s, int l, int r, vector<vector<int>>& dp){

        if(l == r) return 0;
        if(l + 1 == r) return s[l] == s[r] ? 0 : 1;

        if(dp[l][r] != -1) return dp[l][r];

        int res = 1 + min(dfs(s, l + 1, r, dp), dfs(s, l, r - 1, dp));
        if(s[l] == s[r]) res = min(res, dfs(s, l + 1, r - 1, dp));
//        cout << l << "  - " << r << " : " << res << endl;
        return dp[l][r] = res;
    }
};


int main() {

    cout << Solution().isValidPalindrome("abcdeca", 2) << endl;

    return 0;
}

/// Source : https://leetcode.com/problems/valid-palindrome-iii/
/// Author : liuyubobobo
/// Time   : 2019-10-06

#include <iostream>
#include <vector>

using namespace std;


/// Dynamic Programming
/// Time Complexity: O(|s|^2)
/// Space Complexity: O(|s|^2)
class Solution {
public:
    bool isValidPalindrome(string s, int k) {

        vector<vector<int>> dp(s.size(), vector<int>(s.size() + 1, 0));
        for(int i = 0; i + 1 < s.size(); i ++)
            dp[i][2] = (s[i] == s[i + 1] ? 0 : 1);

        for(int len = 3; len <= s.size(); len ++)
            for(int i = 0; i + len <= s.size(); i ++){
                dp[i][len] = 1 + min(dp[i][len - 1], dp[i + 1][len - 1]);
                if(s[i] == s[i + len - 1])
                    dp[i][len] = min(dp[i][len], dp[i + 1][len - 2]);
            }
        return dp[0][s.size()] <= k;
    }
};


int main() {

    cout << Solution().isValidPalindrome("abcdeca", 2) << endl;

    return 0;
}