当前位置:网站首页>Sword finger offer II 019 Delete at most one character to get a palindrome
Sword finger offer II 019 Delete at most one character to get a palindrome
2022-07-06 16:08:00 【mrbone9】
Address :
Power button https://leetcode-cn.com/problems/RQku0D/
This question is related to 680. Verify palindrome string Ⅱ identical
subject :
Given a non empty string s, Please judge if most If you delete a character from the string, you can get a palindrome string .
Example 1:
Input : s = "aba" Output : true |
Example 2:
Input : s = "abca" Output : true explain : You can delete "c" character perhaps "b" character |
Example 3:
Input : s = "abc" Output : false |
Tips :
1 <= s.length <= 105 s It's made up of lowercase letters |
source : Power button (LeetCode)
link :https://leetcode-cn.com/problems/RQku0D
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .
Ideas :
Here are some examples :
Palindrome :abba,abcba
It can be seen that as long as palindromes are deleted 1 Times are still palindromes
Non palindrome :abcb,bcba,cbbcc
The left pointer points to [0], The right pointer points to [len-1], Adjust the left or right pointer once , If the rest is palindromes, then you can
Let's take a longer example :ebcbbececabbacecbbcbe
The left pointer can be adjusted [5] ->[6], The right pointer cannot be adjusted [15]->[14], The total number of adjustments is also one
So the conclusion is , Scan the entire string with double pointers , If it's palindrome perhaps After one adjustment, the substring is also a palindrome , Then the result is ok , Otherwise, you can't
bool checksub(char *s, int i, int j)
{
bool ret = true;
while(i < j)
{
if(s[i] != s[j])
{
ret = false;
break;
}
i++;
j--;
}
return ret;
}
bool validPalindrome(char * s){
int slen = strlen(s);
int i,j;
int maxjudge = 0;
bool ret = true;
i = 0;
j = slen - 1;
while(i < j)
{
if(s[i] != s[j])
{
if( checksub(s, i, j-1) || checksub(s, i+1, j) )
{
ret = true;
break;
}
else
{
ret = false;
break;
}
}
i++;
j--;
}
return ret;
}
边栏推荐
- [exercise-6] (PTA) divide and conquer
- 初入Redis
- [exercise-4] (UVA 11988) broken keyboard = = (linked list)
- Programmers, what are your skills in code writing?
- [exercise-8] (UVA 246) 10-20-30== simulation
- The concept of C language array
- Penetration test 2 --- XSS, CSRF, file upload, file inclusion, deserialization vulnerability
- [exercise-3] (UVA 442) matrix chain multiplication
- China's peripheral catheter market trend report, technological innovation and market forecast
- Find 3-friendly Integers
猜你喜欢
PySide6 信号、槽
【练习-7】Crossword Answers
Penetration test 2 --- XSS, CSRF, file upload, file inclusion, deserialization vulnerability
X-Forwarded-For详解、如何获取到客户端IP
Gartner:关于零信任网络访问最佳实践的五个建议
C language must memorize code Encyclopedia
信息安全-史诗级漏洞Log4j的漏洞机理和防范措施
快速转 TypeScript 指南
Penetration test (7) -- vulnerability scanning tool Nessus
Luogu P1102 A-B number pair (dichotomy, map, double pointer)
随机推荐
F - birthday cake (Shandong race)
基于web的照片数码冲印网站
Borg maze (bfs+ minimum spanning tree) (problem solving report)
Nodejs+vue online fresh flower shop sales information system express+mysql
CEP used by Flink
Research Report of exterior wall insulation system (ewis) industry - market status analysis and development prospect prediction
[exercise-9] Zombie's Treasury test
渗透测试 ( 5 ) --- 扫描之王 nmap、渗透测试工具实战技巧合集
快速转 TypeScript 指南
Interval sum ----- discretization
Penetration test (4) -- detailed explanation of meterpreter command
信息安全-安全专业名称|CVE|RCE|POC|VUL|0DAY
Opencv learning log 18 Canny operator
MySQL授予用户指定内容的操作权限
China exterior wall cladding (EWC) market trend report, technical dynamic innovation and market forecast
【练习-3】(Uva 442)Matrix Chain Multiplication(矩阵链乘)
[teacher Gao UML software modeling foundation] collection of exercises and answers for level 20 cloud class
【高老师软件需求分析】20级云班课习题答案合集
2027. Minimum number of operations to convert strings
[exercise-5] (UVA 839) not so mobile (balance)