Anagram.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "Anagram.ipynb",
      "provenance": [],
      "authorship_tag": "ABX9TyNOF7MFwZvK+yTOK7doxl6I",
      "include_colab_link": true
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "view-in-github",
        "colab_type": "text"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/github/sweetpand/Algorithms/blob/master/Anagram.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Yob8yqT-N2BM",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "s1 = 'fairy tales'\n",
        "s2 = 'rail safety'"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "4TGSKz7vOFWc",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "s1 = s1.replace(\" \", \"\").lower()\n",
        "s2 = s2.replace(\" \", \"\").lower()"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "UAK1XCudOTdb",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 34
        },
        "outputId": "44d83a1c-04da-44ec-d4eb-264478b127f6"
      },
      "source": [
        "O(nlogn)\n",
        "#print(sorted(s1) == sorted(s2))"
      ],
      "execution_count": 3,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "True\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "GS3_eaPeOkmq",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "def is_anagram(s1, s2):\n",
        "  ht = dict()\n",
        "  \n",
        "  if len(s1) != len(s2):\n",
        "    return False\n",
        "\n",
        "  for i in s1:\n",
        "    if i in ht:\n",
        "      ht[i] += 1\n",
        "    else:\n",
        "      ht[i] = 1\n",
        "    \n",
        "  for i in s2:\n",
        "    if i in ht:\n",
        "      ht[i] -= 1\n",
        "    else:\n",
        "      ht[i] = 1\n",
        "\n",
        "  for i in ht:\n",
        "      if ht[i] != 0:\n",
        "          return False\n",
        "  return True"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "rYdl54fqQbFI",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 34
        },
        "outputId": "032cb807-6275-485c-e087-f9f96400232f"
      },
      "source": [
        "print(is_anagram(s1, s2))"
      ],
      "execution_count": 11,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "True\n"
          ],
          "name": "stdout"
        }
      ]
    }
  ]
}