// Given a string which we can delete at most k, return whether you can make a palindrome.
// For example, given 'waterrfetawx' and a k of 2, you could delete f and x to get 'waterretaw'.
#include <iostream>
#include <string>
#include <vector>
using namespace std;
// see this solution for more help: https://www.geeksforgeeks.org/find-if-string-is-k-palindrome-or-not/
int kPalindrome(string str1, string str2, int m, int n)
{
// create a table to store results of subproblems
// by calculating the operations required to form a palindrome
vector<vector<int>> operations = vector<vector<int>>();
for (unsigned i = 0; i <= m; ++i)
{
operations.push_back(vector<int>());
for (unsigned j = 0; j <= n; ++j)
operations[i].push_back(0);
}
// fill the table using a bottom-up method
for (int i = 0; i <= m; ++i)
{
for (int j = 0; j <= n; ++j)
{
// if the first string is empty, store how many operations are required
if (i == 0)
operations[i][j] = j;
// do the same for the second string
else if (j == 0)
operations[i][j] = i;
// if the last characters match, then we can move past them to the remaining substring
else if (str1[i - 1] == str2[j - 1])
operations[i][j] = operations[i - 1][j - 1];
// if the last characters dont match, remove them and find the minimum
// by removing characters from each string (both forward and the reverse)
else
operations[i][j] = 1 + min(operations[i - 1][j], operations[i][j - 1]);
}
}
return operations[m][n];
}
bool isKPalindrome(string str, int k)
{
int len = str.length();
string reverseStr = str;
reverse(reverseStr.begin(), reverseStr.end());
int result = kPalindrome(str, reverseStr, len, len);
// ensure that the minimum operations required are less than k
return result <= k * 2;
}
int main()
{
int k = 2;
string str = "waterrfetawx";
isKPalindrome(str, k) ? cout << "Yay! we can palindrome!" << endl : cout << "Nope... cannot be made into a palindrome" << endl;
return 0;
}
Kommentare