leetCode/06. Recuersion and Call Stack/93. Restore IP Addresses.ipynb

{
 "cells": [
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 93. Restore IP Addresses\n"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A **valid IP address** consists of exactly four integers separated by single dots. Each integer is between `0` and `255` (**inclusive**) and cannot have leading zeros.\n",
    "\n"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- For example, `\"0.1.2.201\"` and `\"192.168.1.1\"` are **valid** IP addresses, but `\"0.011.255.245\"`, `\"192.168.1.312\"` and `\"192.168@1.1\"` are **invalid** IP addresses."
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Given a string `s` containing only digits, return all possible valid IP addresses that can be formed by inserting dots into `s`. You are not allowed to reorder or remove any digits in `s`. You may return the valid IP addresses in **any** order."
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Example 1:**"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- **Input**: s = \"25525511135\"\n",
    "- **Output**: [\"255.255.11.135\",\"255.255.111.35\"]"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Example 2:**\n",
    "\n"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- **Input**: s = \"0000\"\n",
    "- **Output**: [\"0.0.0.0\"]"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Example 3:**"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- **Input**: s = \"101023\"\n",
    "- **Output**: [\"1.0.10.23\",\"1.0.102.3\",\"10.1.0.23\",\"10.10.2.3\",\"101.0.2.3\"]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def restoreIpAddresses(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: List[str]\n",
    "        \"\"\"\n",
    "        res = []\n",
    "\n",
    "        if len(s) > 12:\n",
    "            return res\n",
    "\n",
    "        def backtrack(i, dots, curIP):\n",
    "\n",
    "            if dots == 4 and i == len(s):\n",
    "                res.append(curIP[:-1])\n",
    "                return\n",
    "\n",
    "            if dots > 4:\n",
    "                return\n",
    "\n",
    "            for j in range(i, min(i + 3, len(s))):\n",
    "                if int(s[i:j+1]) < 256 and (i == j or s[0] != \"0\"):\n",
    "                    backtrack(j+1, dots+1, curIP + s[i:j+1] + \".\")\n",
    "\n",
    "        backtrack(0, 0, \"\")\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['255.255.11.135', '255.255.111.35']\n",
      "['0.0.0.0']\n",
      "['1.0.1.023', '1.0.10.23', '1.0.102.3', '1.01.0.23', '1.01.02.3', '1.010.2.3', '10.1.0.23', '10.1.02.3', '10.10.2.3', '101.0.2.3']\n"
     ]
    }
   ],
   "source": [
    "sol=Solution()\n",
    "print(sol.restoreIpAddresses(\"25525511135\"))\n",
    "print(sol.restoreIpAddresses(\"0000\"))\n",
    "print(sol.restoreIpAddresses(\"101023\"))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "sol.restoreIpAddresses(\"25525511135\")"
   ]
  }
 ],
 "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.10.6"
  },
  "orig_nbformat": 4,
  "vscode": {
   "interpreter": {
    "hash": "916dbcbb3f70747c44a77c7bcd40155683ae19c65e1c03b4aa3499c5328201f1"
   }
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}