roma-dxunvrs
35 lines
1.0 KiB
Markdown
35 lines
1.0 KiB
Markdown
Leetcode #680 | Easy | [[Два указателя]]
|
||
## Идея
|
||
Продолжение [[Valid Palindrome]], только теперь можно удалить один символ. При первом несовпадении запускаем вспомогательную функцию, которая допроверяет либо с `l+1 до r`, либо с `l до r-1`
|
||
## [[Big-O]]
|
||
- Время ```O(N)```
|
||
- Память ```O(1)```
|
||
## Код
|
||
```Java
|
||
class Solution {
|
||
public boolean validPalindrome(String s) {
|
||
int l = 0;
|
||
int r = s.length()-1;
|
||
|
||
while (l < r) {
|
||
if (s.charAt(l) != s.charAt(r)) {
|
||
return isPalindrome(s, l+1, r) || isPalindrome(s, l, r-1);
|
||
}
|
||
l++;
|
||
r--;
|
||
}
|
||
return true;
|
||
}
|
||
|
||
boolean isPalindrome(String s, int l, int r) {
|
||
while (l < r) {
|
||
if (s.charAt(l) != s.charAt(r)) {
|
||
return false;
|
||
}
|
||
l++;
|
||
r--;
|
||
}
|
||
return true;
|
||
}
|
||
}
|
||
``` |