Convert a string to a palindrome


  • 0
    T

    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.


  • 2

    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;
      }
      
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.