algorithms/125-valid-palindrome.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "plain-usage",
   "metadata": {},
   "source": [
    "### 判断回文\n",
    "\n",
    "给定一个字符串，请编写一个函数判断该字符串是否回文。如果回文请返回`true`，否则返回`false`。\n",
    "\n",
    "#### 示例1\n",
    "```\n",
    "输入 \"absba\"\n",
    "返回值 true\n",
    "```\n",
    "\n",
    "#### 示例2\n",
    "```\n",
    "输入 \"ranko\"\n",
    "返回值 false\n",
    "```\n",
    "\n",
    "#### 示例3\n",
    "```\n",
    "输入 \"yamatomaya\"\n",
    "返回值 false\n",
    "```\n",
    "\n",
    "#### 示例4\n",
    "```\n",
    "输入 \"a\"\n",
    "返回值 true\n",
    "```\n",
    "\n",
    "#### 备注:\n",
    "\n",
    "> 字符串长度不大于1000000，且仅由小写字母组成"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "alert-upgrade",
   "metadata": {},
   "outputs": [],
   "source": [
    "def judge(s: str) -> bool:\n",
    "    r = ''.join(reversed(s))\n",
    "    return r == s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "transparent-heritage",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "judge(\"absba\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "id": "magnetic-physics",
   "metadata": {},
   "outputs": [],
   "source": [
    "def isPalindrome(s: str) -> bool:\n",
    "    def isValidChar(ch):\n",
    "        return 'a' <= ch <= 'z' or 'A' <= ch <= 'Z' or '0' <= ch <= '9'\n",
    "    \n",
    "    n = len(s)\n",
    "    i, j = 0, n - 1\n",
    "    while i <= j:\n",
    "        c1, c2 = s[i], s[j]\n",
    "        if i < n -1 and not isValidChar(c1):\n",
    "            i += 1\n",
    "            continue\n",
    "        if j > 0 and not isValidChar(c2):\n",
    "            j -= 1\n",
    "            continue\n",
    "            \n",
    "        if isValidChar(c1) and isValidChar(c2) and c1.lower() != c2.lower():\n",
    "            return False\n",
    "        i += 1\n",
    "        j -= 1\n",
    "    return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "id": "otherwise-gabriel",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 39,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "isPalindrome(\"absba\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "id": "basic-stereo",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 40,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "isPalindrome(\"A man, a plan, a canal: Panama\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "id": "bulgarian-comedy",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 41,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "isPalindrome(\"race a car\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "id": "worse-feelings",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 42,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "isPalindrome(\".,\")"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "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.8.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}