# #1 Palindrome Check

###### tags: `String` `Easy`

## Problem
Write a function that takes in a non-empty string and that returns a boolean representing whether the string is a palindrome.

A palindrome is defined as a string that's written the same forward and backward. Note that single-character strings are palindromes.

### Sample Input

string = "abcdcba"

### Sample Output

true // it's written the same forward and backward

<br>

:::spoiler **Optimal Space & Time Complexity**

:::

<br>

:::spoiler Hint 1

:::

<br>

:::spoiler Hint 2

:::

<br>

:::spoiler Hint 3

:::

<br>

<hr/>

## Solutions

### Official

// O(n) time | O(1) space
function isPalindrome(string) {
  let leftIdx = 0;
  let rightIdx = string.length -1;
  
    while(leftIdx < rightIdx){
        if(string[leftIdx] !== string[rightIdx]) return false;
        leftIdx++;
        rightIdx--;
    }
    return true;
}

// Do not edit the line below.
exports.isPalindrome = isPalindrome;

<br>

---

### Everyone's

:::spoiler 月

// Time O(n) Space O(1)
function isPalindrom(string){
  let left = 0, right = string.length - 1;
  while(left < right){
    if(string[left] != string[right]) return false;
    left++;
    right--;
  }
  return true
}

// 可能盡量使用 !== 

:::

<br>

:::spoiler Raiy

//time: O(n) | space: O(1)
function isPalindrome(string) {
  let left = 0;
  let right = string.length -1;

  while(left<right){
    if(string[left] !== string[right]){
      return false
    }
    left++;
    right--;
  }

  return true;
}

:::

<br>

:::spoiler Becky

//time: O(n) | space: O(n)
function isPalindrome(string) {
  let len = string.length;
  let left = 0;
  let right = len - 1;
  let result;
  while(left < right){
    if(string[left] !== string[right]){
      return false;
    }
    left++
    right--
  }
  return true;
}

// result 不需要、 space 應該是 O(1)

:::

<br>

:::spoiler 東

// Time O(n) space O(1), n is the length of string
function isPalindrome(string) {
  let left = 0;
  let right = string.length - 1;
  while (left < right){
    if (string[left] === string[right]){
      left ++;
      right --;
    } else return false;
  }
  return true;
}

:::

<br>

:::spoiler Hao ( use Array -> space O(n) )

function isPalindrome(string) {
  /**
   * O(n) time, O(n) space
   */
  const charArr = string.split('');
  let i = 0;
  let j = charArr.length - 1;
  while (i <= j) {
    if (charArr[i] !== charArr[j]) return false;
    i += 1;
    j -= 1;
  }
  return true;
}

:::

<br>

:::spoiler YC

// time: O(n) space: O(1);
function isPalindrome(string) {
  let left = 0;
  let right = string.length - 1;
  while(left < right){
    if(string[left] !== string[right]) return false;
      left++;
      right--;
  }
  return true; 
}

:::

<br>

:::spoiler SOL

// time: O(n) space: O(1);
const isPalindrome = (string) => {
  let left = 0,
    right = string.length - 1;
  while (left <= right) {
    if (string.charAt(left) !== string.charAt(right)) {
      return false;
    }
    left++;
    right--;
  }
  return true;
};

:::

---

## Supplement / Discussion
1. 回文應用 -> DNA、RNA
2. 官方答案 1 O(n^2) 源於 ： 字串做類似 += 處理時，都會先 copy 再處理
3. 官方答案 3 使用遞迴 -> 使用暫存堆疊(Stack)，需要額外的儲存空間
4. Leetcode 更進階的題目 https://leetcode.com/problems/valid-palindrome/
* 回文對象僅包含字母、數字
* 使用 built-in method : charCodeAt()