125_Valid_Palindrome.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "da9b6d89",
   "metadata": {},
   "source": [
    "A phrase is a palindrome if, after converting all uppercase letters into lowercase letters and removing all non-alphanumeric characters, it reads the same forward and backward. Alphanumeric characters include letters and numbers.\n",
    "\n",
    "Given a string s, return true if it is a palindrome, or false otherwise.\n",
    "\n",
    " \n",
    "\n",
    "Example 1:\n",
    "\n",
    "Input: s = \"A man, a plan, a canal: Panama\"\n",
    "Output: true\n",
    "Explanation: \"amanaplanacanalpanama\" is a palindrome.\n",
    "Example 2:\n",
    "\n",
    "Input: s = \"race a car\"\n",
    "Output: false\n",
    "Explanation: \"raceacar\" is not a palindrome.\n",
    "Example 3:\n",
    "\n",
    "Input: s = \" \"\n",
    "Output: true\n",
    "Explanation: s is an empty string \"\" after removing non-alphanumeric characters.\n",
    "Since an empty string reads the same forward and backward, it is a palindrome.\n",
    " \n",
    "\n",
    "Constraints:\n",
    "\n",
    "1 <= s.length <= 2 * 105\n",
    "s consists only of printable ASCII characters."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "id": "06429071",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['a', 'm', 'a', 'n', 'a', 'p', 'l', 'a', 'n', 'a', 'c', 'a', 'n', 'a', 'l', 'p', 'a', 'n', 'a', 'm', 'a']\n",
      "['a', 'm', 'a', 'n', 'a', 'p', 'l', 'a', 'n', 'a', 'c', 'a', 'n', 'a', 'l', 'p', 'a', 'n', 'a', 'm', 'a']\n",
      "True\n"
     ]
    }
   ],
   "source": [
    "# s = \"A man, a plan, a canal: Panama\"\n",
    "\n",
    "filtered_chars = filter(lambda ch: ch.isalnum(), s.lower())\n",
    "rev_string= s[::-1]\n",
    "filtered_rev_chars = filter(lambda ch: ch.isalnum(), rev_string.lower())\n",
    "\n",
    "# print(list(filtered_chars))\n",
    "# print(list(filtered_rev_chars))\n",
    "\n",
    "if list(filtered_rev_chars) == list(filtered_chars):\n",
    "    print(True)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1cf7e3c0",
   "metadata": {},
   "source": [
    "### Pointers solution"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "id": "19e801a6",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n"
     ]
    }
   ],
   "source": [
    "s = \"race a car\"\n",
    "\n",
    "#take two pointers one from the begining and one from the ending \n",
    "i ,j =0, len(s)-1\n",
    "\n",
    "#move both the pointers from opposite directions\n",
    "#note: pallindrome has two equal parts from left and right\n",
    "\n",
    "while i<j:\n",
    "\n",
    "    if not (s[i].isalnum()):\n",
    "        i =+1\n",
    "    if not(s[j].isalnum()):\n",
    "        j=-1\n",
    "    if (s[i].lower() != s[j].lower()):\n",
    "        print(False)\n",
    "    i=+1\n",
    "    j=-1\n",
    "    \n",
    "print(True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "f9094ce6",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.9.7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}