PalindromeBigO.java

// O(n + n + n/2)
// O(2n + n/2)
// O(2.5n)
// O(n)
public boolean isPalindrome(String input) {
  // replaceAll - n times
  input = input.replaceAll("\\s","");
  // replaceAll - n times
  int n = input.length();

  // for - n/2 times
  for (int i = 0; i < (n/2); i ++){
    if (input.charAt(i) != input.charAt(n-i-1)) {
      return false;
    }
  }
  return true;
}


// O(n + n + n + n + n)
// O(5n)
// O(n)
public boolean isPalindrome(String input) {

  // replaceAll - n times
  String word = input.replaceAll("\\s+","");

  // reverse - n times
  // replaceAll - n times
  // toString - n times
  String reversedWord = new StringBuilder(input).reverse().toString().replaceAll("\\s+","");
  System.out.println(word);
  System.out.println(reversedWord);

  // equals - n times
  if(word.equals(reversedWord)) {
    return true;
  } else {
   return false;
  }
}