Given a string S, whether we can convert it to a palindrome by adding a character inside the string.
Please return false or true.
For example:
Given "ab", return true.
Given "abcd", return false.
Maybe there's a better way to solve this problem, I just want to share my solution here. The idea is straightforward, check from both ends of the input string till we find a mismatch at s[i]
and s[j]
, then try to append s[i]
to s[i...j]
and see if it forms a palindrome, if not, try to prepend s[j]
to s[i...j]
and see if it works. Time complexity is O(n)
.
public class Solution {
public boolean canConvert(String s) {
int i = 0, j = s.length() - 1;
while (i < j && s.charAt(i) == s.charAt(j)) {
i++; j--;
}
return i >= j ||
isPalindrome(s.charAt(j) + s.substring(i, j + 1)) ||
isPalindrome(s.substring(i, j + 1) + s.charAt(i));
}
boolean isPalindrome(String s) {
int i = 0, j = s.length() - 1;
while (i < j && s.charAt(i) == s.charAt(j)) {
i++; j--;
}
return i >= j;
}
}