Question:
A k-palindrome is a string which transforms into a palindrome on removing at most k characters.
Given a string S, and an interger K, print “YES” if S is a k-palindrome; otherwise print “NO”.
Constraints:
S has at most 20,000 characters.
0<=k<=30
Sample Test Case#1:
Input – abxa 1
Output – YES
Sample Test Case#2:
Input – abdxa 1
Output – No
one solution:
Let's say p[n] is a palindrom with lenght n. Let l will be begining, end e the end of a palindrom. Then we can see that:
1) p[l] == p[h], then we need to check p[l+1] == p[h – 1], i.e abcba, where p[l] == a == p[h]
2a) p[l] != p[h], then we need to check p[l+1],p[h] (we removed p[l])
2b) p[l] != p[h], then we need to check p[l], p[h-1], (we removed p[h])
bool isKPalindrom(string input, int k) { int answers[input.size() + 1][input.size() + 1]; int N = input.size(); for(int i = 0; i <= N; i++) for(int j = 0; j <= N; j++) answers[i][j] = 0; for(int gap = 1; gap <= N; gap++) { int l = 1; int h = l + gap; for(; h <= N; l++, h++) { if(input[l-1] == input[h - 1]) answers[l][h] = answers[l+1][h-1]; else answers[l][h] = 1 + min(answers[l+1][h], answers[l][h-1]); } } return answers[1][N] <= k; }
The complexity is O(n^2).
Another solution:
The question asks if we can transform the given string S into its reverse deleting at most K letters.
We could modify the traditional Edit-Distance algorithm, considering only deletions, and check if this edit distance is <= K. There is a problem though. S can have length = 20,000 and the Edit-Distance algorithm takes O(N^2). Which is too slow.
(From here on, I'll assume you're familiar with the Edit-Distance algorithm and its DP matrix)
However, we can take advantage of K. We are only interested *if* manage to delete K letters. This means that any position more than K positions away from the main diagonal is useless because its edit distance must exceed those K deletions.
Since we are comparing the string with its reverse, we will do at most K deletions and K insertions (to make them equal). Thus, we need to check if the ModifiedEditDistance is <= 2*K
Here's the code:
int kpalindrome(string &a, int k){ int asize = a.size(); string b = a; reverse(b.begin(), b.end()); int bsize = asize; vector<vector<int> > dp(asize+1, vector<int>(bsize+1, 1000)); for(int i = 0; i <= asize; i++){ dp[i][0] = i; dp[0][i] = i; } for(int i = 1; i <= asize; i++){ for(int j = max(1, i-k); j <= min(bsize, i+k); j++){ if(a[i-1] == b[j-1]){ dp[i][j] = dp[i-1][j-1]; } dp[i][j] = min(dp[i][j], dp[i-1][j]+1); dp[i][j] = min(dp[i][j], dp[i][j-1]+1); } } if(dp[asize][bsize]<= 2*k) return dp[asize][bsize]; else return -1; } int _tmain(int argc, _TCHAR* argv[]) { string a = "abxa"; int ret = kpalindrome(a, 1); cout<<ret<<endl; return 0; }
We only process 2*K+1 columns per row. So this algorithm works in O(N*K) which is fast enough.
From:
相关推荐
...The number of questions is increasing recently. Here is the classification of all `468` questions. ...I'll keep updating for full summary and better solutions....|-----|---------------- | --------------- |...
典型的题目有《有效的回文字符串》(https://leetcode-cn.com/problems/valid-palindrome/)、《有效的回文字符串 II》(https://leetcode-cn.com/problems/valid-palindrome-ii/)以及《最长回文子串》...
9. Palindrome Number 11. Container With Most Water 13. Roman to Integer 15. 3Sum 16. 3Sum Closest 17. Letter Combinations of a Phone Number 18. 4Sum 19. Remove Nth Node From End of List 20. Valid ...
- **样题参考**:`kth-largest-element-in-an-array`要求找到数组中第k大的元素,`merge-sorted-array`是合并两个已排序的数组,`largest-number`要求构建最大的数字,`maximum-gap`则是在排序数组中找出最大间隔。...
5. Closest Palindrome 6. Check Array Contains Contigous Integer 7. Pairs with Positive and Negative Values 8. Maximum Tip Calculator 9. Prime Number of Set Bits 10. Reverse Each Word in String 11. ...
- Valid Palindrome(回文字符串验证) - Longest Palindromic Substring(最长回文子串) - Space Replacement(URL化) - Wildcard Matching(通配符匹配) - Length of Last Word(最后一个单词的长度) - ...
Palindrome Number 11. Container With Most Water 12. Integer to Roman 13. Roman to Integer 14. Longest Common Prefix 15. 3Sum 20. Valid Parentheses 21. Merge Two Sorted Lists 22. Generate Parentheses ...
leetcode中325题python leetcode 以 参考 和 Hash相关 1_两数之和 387_字符串中的第一个唯一字符 链表操作 2 ...删除链表的倒数第N个节点 ...k个一组翻转链表 ...palindrome-linked-list 双指针遍历/滑动
在提供的代码中,有两段相似的`Palindrome_Test`函数,它们都使用了栈和队列来辅助判断。算法的基本步骤如下: 1. 初始化一个空栈`S`和一个空队列`Q`。 2. 读取输入的字符序列,直到遇到结束符'@'或字符串结束。 3...
1. **验证回文串**(Valid Palindrome) - 知识点:字符串处理,双指针法 - 解题思路:通过两个指针,一个从左向右,一个从右向左,比较字符是否相等。如果遇到不相等的字符,可以通过忽略大小写和非字母数字字符...
在这个项目中,学生需要建立一个名为SP的类,用于计算特定公式`f(n,k)=1^k+2^k+3^k+....+n^k`。其中,`n`和`k`是公式的参数。项目的关键知识点包括: 1. **类的定义**:通过`class SP`定义了一个包含私有数据成员`n...
[回文链表](md/Palindrome Linked List.md) - 2015-10-06 [数字一](md/数字一.md) - 2015-10-06 [使用栈实现队列](md/使用栈实现队列.md) - 2015-10-06 [BST 中的第 K 个最小元素](md/BST.md 中的第 K 个最小元素) -...
- **验证回文字符串(Valid Palindrome)**: 判断一个字符串是否是回文。 - **最长回文子串(Longest Palindromic Substring)**: 找出字符串中最长的回文子串。 - **通配符匹配(Wildcard Matching)**: 实现通配符‘*’...
- `int palindrome(int a)` 定义了一个名为`palindrome`的函数,用于判断输入的整数是否为回文数。 2. **数值操作**: - `b = b * 10 + (c % 10);` 使用数学运算实现数字的反转。 - `c = c / 10;` 将原数除以10,...
#### Palindrome Pairs(回文对) - **问题描述**:给定一系列单词,找出其中形成回文的单词对。 - **解决思路**: - 构建Trie树,便于查找前缀后缀匹配。 - 遍历每个单词,检查是否满足条件。 #### Find Median ...
- **有效的回文字符串(Valid Palindrome)** - 判断一个字符串是否是回文字符串。 - **最长回文子串(Longest Palindromic Substring)** - 寻找字符串中最长的回文子串。 ##### 2. 整型数组 - **移除元素(Remove ...
判断链表是否为回文链表 ...)=k,其中k=1到numOfRows当k>=numOfRows时,对应中间的元素,存储位置应该是(numOfRows-1)-(i-(numOfRows-1)) #longest common prefix 最长的公共前缀长度不会超过列表中最短的字符
- Kth Largest Element in an Array:在未排序的数组中找到第k大的元素。 - Binary Search:二分查找法。 - First Position of Target:在有序数组中找到目标值的第一个位置。 - Search Insert Position:在排序数组...