当前位置： 面试刷题>> 特殊回文字符串 (经典算法题500道)
**题目描述补充**：
题目：特殊回文字符串
给定一个字符串 `s`，我们需要判断该字符串是否可以通过至多删除一个字符后成为回文字符串。回文字符串是指正读和反读都相同的字符串。
**示例**：
- 输入：`s = "aba"`
- 输出：`true` （因为 `aba` 已经是回文字符串）
- 输入：`s = "abca"`
- 输出：`true` （通过删除 'c'，字符串可以变成 "aba"，这是一个回文字符串）
- 输入：`s = "abc"`
- 输出：`false` （无论删除哪个字符，都无法形成回文字符串）
**解题思路**：
这个问题可以通过双指针法来解决。初始化两个指针，一个指向字符串的开头，另一个指向字符串的末尾。然后，我们比较这两个指针所指的字符是否相等。如果相等，我们就将两个指针都向中间移动；如果不等，我们就尝试删除其中一个指针所指的字符（即左指针右移一位或右指针左移一位），并递归地检查剩余的子串是否为回文字符串。为了避免递归带来的栈溢出和提高效率，我们可以将递归改为迭代，并使用一个辅助函数来检查子串是否为回文字符串。
**PHP 示例代码**：
```php
function validPalindrome($s) {
$left = 0;
$right = strlen($s) - 1;
while ($left < $right) {
if ($s[$left] !== $s[$right]) {
return isPalindrome($s, $left + 1, $right) || isPalindrome($s, $left, $right - 1);
}
$left++;
$right--;
}
return true;
}
function isPalindrome($s, $left, $right) {
while ($left < $right) {
if ($s[$left] !== $s[$right]) {
return false;
}
$left++;
$right--;
}
return true;
}
// 示例调用
echo validPalindrome("aba") ? "true" : "false"; // 输出 true
echo "\n";
echo validPalindrome("abca") ? "true" : "false"; // 输出 true
echo "\n";
echo validPalindrome("abc") ? "true" : "false"; // 输出 false
```
**Python 示例代码**：
```python
def validPalindrome(s: str) -> bool:
def is_palindrome(left, right):
while left < right:
if s[left] != s[right]:
return False
left, right = left + 1, right - 1
return True
left, right = 0, len(s) - 1
while left < right:
if s[left] != s[right]:
return is_palindrome(left + 1, right) or is_palindrome(left, right - 1)
left, right = left + 1, right - 1
return True
# 示例调用
print(validPalindrome("aba")) # 输出 True
print(validPalindrome("abca")) # 输出 True
print(validPalindrome("abc")) # 输出 False
```
**JavaScript 示例代码**：
```javascript
function validPalindrome(s) {
function isPalindrome(left, right) {
while (left < right) {
if (s[left] !== s[right]) {
return false;
}
left++;
right--;
}
return true;
}
let left = 0, right = s.length - 1;
while (left < right) {
if (s[left] !== s[right]) {
return isPalindrome(left + 1, right) || isPalindrome(left, right - 1);
}
left++;
right--;
}
return true;
}
// 示例调用
console.log(validPalindrome("aba")); // 输出 true
console.log(validPalindrome("abca")); // 输出 true
console.log(validPalindrome("abc")); // 输出 false
```
**码小课**：在码小课网站中，你可以找到更多关于算法和数据结构的课程内容，包括动态规划、搜索算法、图论、字符串处理等多个专题，帮助你深入学习编程和算法知识。