План курса / Все задачи / Алгоритмы и структуры данных
Почти палиндром
средне
# решено
Дана строка s. Нужно вернуть true, если из неё можно удалить не более одного символа, чтобы получился палиндром, и false — в противном случае.
Палиндром — это слово или фраза, которые читаются одинаково слева направо и справа налево.
Пример 1:
Ввод: s = "abca"
Вывод: true
Объяснение: Если удалить символ 'b', строка станет палиндромом: "aca"
Пример 2:
Ввод: s = "racecar"
Вывод: true
Объяснение: cтрока уже является палиндромом
Пример 3:
Ввод: s = "deeee"
Вывод: true
Объяснение: удалив 'd', строка станет палиндромом: "eeee"
Ограничения:
len(s) >= 1
public class Solution {
// Проверяет, является ли подстрока s[l..r] палиндромом
private static bool IsSubstringPalindrome(string s, int l, int r) {
while (l < r) {
if (s[l] != s[r]) {
return false;
}
l++;
r--;
}
return true;
}
public static bool IsAlmostPalindrome(string s) {
for (int l = 0, r = s.Length - 1; l < r; l++, r--) {
if (s[l] != s[r]) {
// Пробуем удалить символ либо слева, либо справа
return IsSubstringPalindrome(s, l + 1, r) ||
IsSubstringPalindrome(s, l, r - 1);
}
}
// Строка уже палиндром
return true;
}
}
using namespace std;
// Проверяет, является ли подстрока s[l..r] палиндромом
bool isSubstringPalindrome(string &s, int l, int r) {
while (l < r) {
if (s[l] != s[r]) {
return false;
}
l++;
r--;
}
return true;
}
bool isAlmostPalindrome(string &s) {
for (int l = 0, r = s.size() - 1; l < r; l++, r--) {
if (s[l] != s[r]) {
// Пробуем удалить символ либо слева, либо справа
return isSubstringPalindrome(s, l + 1, r) ||
isSubstringPalindrome(s, l, r - 1);
}
}
// Строка уже палиндром
return true;
}
package main
// Проверяет, является ли подстрока s[l..r] палиндромом
func isSubstringPalindrome(s string, l int, r int) bool {
for l < r {
if s[l] != s[r] {
return false
}
l++
r--
}
return true
}
func isAlmostPalindrome(s string) bool {
for l, r := 0, len(s)-1; l < r; l, r = l+1, r-1 {
if s[l] != s[r] {
// Пробуем удалить символ либо слева, либо справа
return isSubstringPalindrome(s, l+1, r) ||
isSubstringPalindrome(s, l, r-1)
}
}
// Строка уже палиндром
return true
}
import java.util.*;
public class Solution {
// Проверяет, является ли подстрока s[l..r] палиндромом
private boolean isSubstringPalindrome(String s, int l, int r) {
for (; l < r; l++, r--) {
if (s.charAt(l) != s.charAt(r)) {
return false;
}
}
return true;
}
public boolean isAlmostPalindrome(String s) {
for (int l = 0, r = s.length() - 1; l < r; l++, r--) {
if (s.charAt(l) != s.charAt(r)) {
// Пробуем удалить символ либо слева, либо справа
return isSubstringPalindrome(s, l + 1, r) ||
isSubstringPalindrome(s, l, r - 1);
}
}
// Строка уже палиндром
return true;
}
}
from typing import *
# Проверяет, является ли подстрока s[l..r] палиндромом
def is_substring_palindrome(s: str, l: int, r: int) -> bool:
while l < r:
if s[l] != s[r]:
return False
l += 1
r -= 1
return True
def is_almost_palindrome(s: str) -> bool:
for l, r in zip(range(len(s)), reversed(range(len(s)))):
if l >= r:
break
if s[l] != s[r]:
# Пробуем удалить символ либо слева, либо справа
return is_substring_palindrome(s, l + 1, r) or \
is_substring_palindrome(s, l, r - 1)
# Строка уже палиндром
return True
/**
* Проверяет, является ли подстрока s[l..r] палиндромом
* @param {string} s
* @param {number} l
* @param {number} r
* @returns {boolean}
*/
function isSubstringPalindrome(s, l, r) {
while (l < r) {
if (s[l] !== s[r]) {
return false;
}
l++;
r--;
}
return true;
}
/**
* @param {string} s
* @returns {boolean}
*/
export function isAlmostPalindrome(s) {
let l = 0;
let r = s.length - 1;
while (l < r) {
if (s[l] !== s[r]) {
// Пробуем удалить символ либо слева, либо справа
return isSubstringPalindrome(s, l + 1, r) ||
isSubstringPalindrome(s, l, r - 1);
}
l++;
r--;
}
// Строка уже палиндром
return true;
}