[LC] Isomorphic Strings.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Given two strings s and t, determine if they are isomorphic.\n",
    "\n",
    "Two strings are isomorphic if the characters in s can be replaced to get t.\n",
    "\n",
    "All occurrences of a character must be replaced with another character while preserving the order of characters. No two characters may map to the same character but a character may map to itself.\n",
    "\n",
    "For example,\n",
    "Given \"egg\", \"add\", return true.\n",
    "\n",
    "Given \"foo\", \"bar\", return false.\n",
    "\n",
    "Given \"paper\", \"title\", return true.\n",
    "\n",
    "Note:\n",
    "You may assume both s and t have the same length"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 89,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def isIsomorphic(self, s, t):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :type t: str\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        if len(s) ==0:\n",
    "            return True\n",
    "        d = {}\n",
    "        for i in range(len(s)):\n",
    "            if s[i] in d:\n",
    "                if d[s[i]] != t[i]:\n",
    "                    return False\n",
    "            else:\n",
    "                if t[i] in d:\n",
    "                    if d[t[i]] != s[i]:\n",
    "                        return False\n",
    "                d[s[i]] = t[i]\n",
    "        tail = len(s)-1\n",
    "        return d[s[tail]] == t[tail]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[0, 1, 0, 3, 4]\n",
      "[0, 1, 0, 3, 4]\n"
     ]
    }
   ],
   "source": [
    "s = 'paper'\n",
    "t = 'title'\n",
    "print [s.find(i) for i in s]\n",
    "print [t.find(j) for j in t]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def isIsomorphic(self, s, t):\n",
    "        print [s.find(i) for i in s] \n",
    "        print [t.find(j) for j in t]\n",
    "        return [s.find(i) for i in s] == [t.find(j) for j in t]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 90,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "isIsomorphic\n"
     ]
    }
   ],
   "source": [
    "sol = Solution()\n",
    "if sol.isIsomorphic (\"ab\",\"bb\"):\n",
    "    print \"isIsomorphic\"\n",
    "else:\n",
    "    print \"not isIsomorphic\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "97\n"
     ]
    }
   ],
   "source": [
    "print ord('a')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 65,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def isIsomorphic(self, s, t):\n",
    "        if len(s) ==0:\n",
    "            return True\n",
    "        ds = \n",
    "        dt = \n",
    "        for i in range(len(s)):\n",
    "            if s[i] in ds and t[i] in dt:\n",
    "                if ds[s[i]] != dt[t[i]]:\n",
    "                    return False\n",
    "            ds[s[i]] = i+1\n",
    "            dt[t[i]] = i+1\n",
    "        print ds\n",
    "        print dt\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 100,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "at:  5\n",
      "not isIsomorphic\n"
     ]
    }
   ],
   "source": [
    "sol = Solution3()\n",
    "if sol.isIsomorphic (\"axbbbcxzxvxv\",\"cyaaaccxzvxvxs\"):\n",
    "    print \"isIsomorphic\"\n",
    "else:\n",
    "    print \"not isIsomorphic\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 99,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "class Solution3(object):\n",
    "    def isIsomorphic(self, s, t):\n",
    "        # following two arrays, index: ascII of the char, value: last seen index in string\n",
    "        m1 = [0]*256\n",
    "        m2 = [0]*256\n",
    "        for i in range(len(s)):\n",
    "            if m1[ord(s[i])] != m2[ord(t[i])]:\n",
    "                print \"at: \",i\n",
    "                return False\n",
    "            m1[ord(s[i])] = i+1\n",
    "            m2[ord(t[i])] = i+1\n",
    "        return True"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.10"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}