Palindrome II

Problem

Given a string s. Test whether you can make it a palindrome by deleting at most one character.

Example 1:

Input: "aba"

Output: True

Example 2:

Input: "abca"

Output: True

Explanation: You could delete the character 'c'.

Example 3:

Input: "abcbcca"

Output: False

Solution

We can use two pointers, one from left towards right, the other from right towards left. Whenever the characters at the pointers' position is different, we will try to fix it by removing the character at the left pointer. If that fix didn't work, then we try to fix it by removing the character at the right pointer. If both fixes fail, we return false, otherwise return true.

public class PalindromeII {
  public static boolean canBeFixed(String str) {//bcbcc
    if(str == null) return false;
    if(str.length() == 0 || str.length() == 1) return true;
    int lo = 0;
    int hi = str.length() - 1;
    while(lo <= hi) {//1 5
      if(str.charAt(lo) != str.charAt(hi)) {
        if(isPalindrome(str.substring(lo+1, hi+1))) return true;
        if(isPalindrome(str.substring(lo, hi))) return true;
        else return false;
      }
      lo++;
      hi--;
    }
    return true;   
  }
  private static boolean isPalindrome(String str) {//bcbc
    int lo = 0;
    int hi = str.length() - 1;
    while(lo <= hi) {//1 2
      if(str.charAt(lo++) != str.charAt(hi--)) {
        return false;
      }
    }
    return true;
  }
  public static void main(String...args) {
    System.out.println(canBeFixed("abca"));
    System.out.println(canBeFixed("abcbcca"));
    System.out.println(canBeFixed("aba"));
  }
}

Time complexity O(N), space complexity O(1).