By Long Luo

Here shows 3 Approaches to slove this problem: Brue Force, Recursion and Two Pointers.

Brue Force

Let’s start from the simplest method:

• if $len(str) \le 2$, definitely return $\textit{true}$;
• if the string is a palindrome, return $\textit{true}$;
• if not, enumerate each position as the deleted position, and then check the remaining strings is it a palindrome.

Time complexity of this approach is $O(n^2)$, time limit will be exceeded.

Analysis

• Time Complexity: $O(n^2)$
• Space Complexity: $O(1)$

Recursion

Recursion solution is also easy, it is silimar to the two pointers approach.

Analysis

• Time Complexity: $O(n)$
• Space Complexity: $O(n / 2)$

Two Pointers

An efficient way to check if a string is a palindrome is to use two pointers.

If the characters pointed to by the two pointers are different, one of the two characters must be deleted.

At this time, we can divide it into two cases:

1. delete the character corresponding to the left pointer, leaving the substring $s[low+1:high]$;
2. delete the character corresponding to the right pointer, leaving the substring $s[low:high−1]$.

When at least one of the two substrings is a palindrome, it means that the original string becomes a palindrome after deleting one character.

Analysis

• Time Complexity: $O(n)$.
• Space Complexity: $O(1)$.

All suggestions are welcome.
If you have any query or suggestion please comment below.
Please upvote👍 if you like💗 it. Thank you:-)

Explore More Leetcode Solutions. 😉😃💗