String.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# String"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## <font color=red>8. String to Integer (atoi)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Implement atoi to convert a string to an integer.\n",
    "\n",
    "Hint: Carefully consider all possible input cases. If you want a challenge, please do not see below and ask yourself what are the possible input cases.\n",
    "\n",
    "Notes: It is intended for this problem to be specified vaguely (ie, no given input specs). You are responsible to gather all the input requirements up front.\n",
    "\n",
    "Requirements for atoi:\n",
    "\n",
    "The function first discards as many whitespace characters as necessary until the first non-whitespace character is found. Then, starting from this character, takes an optional initial plus or minus sign followed by as many numerical digits as possible, and interprets them as a numerical value.\n",
    "\n",
    "The string can contain additional characters after those that form the integral number, which are ignored and have no effect on the behavior of this function.\n",
    "\n",
    "If the first sequence of non-whitespace characters in str is not a valid integral number, or if no such sequence exists because either str is empty or it contains only whitespace characters, no conversion is performed.\n",
    "\n",
    "If no valid conversion could be performed, a zero value is returned. If the correct value is out of the range of representable values, INT_MAX (2147483647) or INT_MIN (-2147483648) is returned.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def myAtoi(self, str):\n",
    "        \"\"\"\n",
    "        :type str: str\n",
    "        :rtype: int\n",
    "        \"\"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 59,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "ename": "TypeError",
     "evalue": "'str' object is not callable",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mTypeError\u001b[0m                                 Traceback (most recent call last)",
      "\u001b[0;32m<ipython-input-59-ed9349f02f71>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m()\u001b[0m\n\u001b[0;32m----> 1\u001b[0;31m \u001b[0mfilter\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m' '\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0;34m'ab'\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[0;31mTypeError\u001b[0m: 'str' object is not callable"
     ]
    }
   ],
   "source": [
    "filter(' ','ab')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 38. Count and Say"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The count-and-say sequence is the sequence of integers beginning as follows:\n",
    "1, 11, 21, 1211, 111221, ...\n",
    "\n",
    "1 is read off as \"one 1\" or 11.\n",
    "11 is read off as \"two 1s\" or 21.\n",
    "21 is read off as \"one 2, then one 1\" or 1211.\n",
    "\n",
    "Given an integer n, generate the nth sequence.\n",
    "\n",
    "Note: The sequence of integers will be represented as a string."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution: Since the nth sequence is constructed from (n-1)th sequence. Naturally we consider a recursive solution."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def countAndSay(self, n):\n",
    "        \"\"\"\n",
    "        :type n: int\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        if n==1:\n",
    "            return str(1)\n",
    "        # n-1 th sequence\n",
    "        last_seq=self.countAndSay(n-1)\n",
    "        len_last=len(last_seq)\n",
    "        result=''\n",
    "        count=1\n",
    "        for i in xrange(1,len_last):\n",
    "            if last_seq[i]==last_seq[i-1]:\n",
    "                count+=1\n",
    "            else:\n",
    "                result+=str(count)+str(last_seq[i-1])\n",
    "                count=1\n",
    "        result+=str(count)+str(last_seq[-1])\n",
    "        \n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'11'"
      ]
     },
     "execution_count": 56,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "o=Solution()\n",
    "o.countAndSay(2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The time complexity of the above solution is O(n^2). The space complexity is O(n). We could avoid recursion by just recording the previous string in the new loop as in the discussion solution:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "     def countAndSay(self, n):\n",
    "        s = '1'\n",
    "        for _ in range(n-1):\n",
    "            let, temp, count = s[0], '', 0\n",
    "            for l in s:\n",
    "                if let == l:\n",
    "                    count += 1\n",
    "                else:\n",
    "                    temp += str(count)+let\n",
    "                    let = l\n",
    "                    count = 1\n",
    "            temp += str(count)+let\n",
    "            s = temp\n",
    "        return s"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 58. Length of Last Word"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Given a string s consists of upper/lower-case alphabets and empty space characters ' ', return the length of last word in the string.\n",
    "\n",
    "If the last word does not exist, return 0.\n",
    "\n",
    "Note: A word is defined as a character sequence consists of non-space characters only.\n",
    "\n",
    "For example, \n",
    "Given s = \"Hello World\",\n",
    "return 5."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def lengthOfLastWord(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        count=0\n",
    "        i=len(s)-1\n",
    "        space_at_last=True\n",
    "        while i>=0:\n",
    "            if s[i]!=' ':\n",
    "                count+=1\n",
    "                i-=1\n",
    "                space_at_last=False\n",
    "            elif space_at_last:\n",
    "                i-=1\n",
    "            else:\n",
    "                break\n",
    "            \n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a='    '\n",
    "o=Solution()\n",
    "o.lengthOfLastWord(a)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 67. Add Binary"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Given two binary strings, return their sum (also a binary string).\n",
    "\n",
    "For example,\n",
    "a = \"11\"\n",
    "b = \"1\"\n",
    "\n",
    "Return \"100\".\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def addBinary(self, a, b):\n",
    "        \"\"\"\n",
    "        :type a: str\n",
    "        :type b: str\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        a=list(a)\n",
    "        b=list(b)\n",
    "        a.reverse()\n",
    "        b.reverse()\n",
    "        add=0\n",
    "        len_a=len(a)\n",
    "        len_b=len(b)\n",
    "        result=[]\n",
    "        for i in range(max(len_a,len_b)):\n",
    "            d1=int(a[i]) if i<len_a else 0\n",
    "            d2=int(b[i]) if i<len_b else 0\n",
    "            d=d1+d2+add\n",
    "            if d<2:\n",
    "                add=0\n",
    "                result.append(str(d))\n",
    "            else:\n",
    "                add=1\n",
    "                result.append(str(d-2))\n",
    "        # last digit\n",
    "        if add==1:\n",
    "            result.append('1')\n",
    "        result.reverse()\n",
    "        return ''.join(result)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'1'"
      ]
     },
     "execution_count": 47,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "o=Solution()\n",
    "o.addBinary('0','1')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Discussion solution:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Solution:\n",
    "    def addBinary(self, a, b):\n",
    "        return bin(eval('0b' + a) + eval('0b' + b))[2:]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## <font color=red>93. Restore IP Addresses"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Given a string containing only digits, restore it by returning all possible valid IP address combinations.\n",
    "\n",
    "For example:\n",
    "Given \"25525511135\",\n",
    "\n",
    "return [\"255.255.11.135\", \"255.255.111.35\"]. (Order does not matter)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def restoreIpAddresses(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: List[str]\n",
    "        \"\"\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## <font color=red>151. Reverse Words in a String"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Given an input string, reverse the string word by word.\n",
    "\n",
    "For example,\n",
    "Given s = \"the sky is blue\",\n",
    "return \"blue is sky the\".\n",
    "\n",
    "Update (2015-02-12):\n",
    "For C programmers: Try to solve it in-place in O(1) space.\n",
    "\n",
    "click to show clarification.\n",
    "\n",
    "Clarification:\n",
    "\n",
    "* What constitutes a word? A sequence of non-space characters constitutes a word.\n",
    "\n",
    "* Could the input string contain leading or trailing spaces? Yes. However, your reversed string should not contain leading or trailing spaces.\n",
    "\n",
    "* How about multiple spaces between two words? Reduce them to a single space in the reversed string.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution: The strategy is as follows:\n",
    "\n",
    "1. Store the word one by one in a list. In this process, we skip the leading spaces.\n",
    "2. pop the word from the list to construct the new reversed string. If it is the leading word, no space is added in front; else we add a front space."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 111,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def reverseWords(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        if s=='':\n",
    "            return ''\n",
    "        n=len(s)\n",
    "        # skip leading white spaces\n",
    "        start=0\n",
    "        end=n-1\n",
    "        while start<n and s[start]==' ':\n",
    "            start+=1\n",
    "        if start==n:\n",
    "            return ''\n",
    "        while end>=0 and s[end]==' ':\n",
    "            end-=1\n",
    "        # construct word_list\n",
    "        word_list=[]\n",
    "        last_start=start\n",
    "        for i in range(start+1,end+1):\n",
    "            if s[i]==' ' and s[i-1]!=' ':\n",
    "                word_list.append(s[last_start:i])\n",
    "                last_start=i+1\n",
    "            elif s[i]==' ' and s[i-1]==' ':\n",
    "                last_start=i+1\n",
    "        # append last word\n",
    "        word_list.append(s[last_start:end+1])\n",
    "   \n",
    "        # construct reversed string\n",
    "        reversed_string=word_list.pop()\n",
    "        while word_list:\n",
    "            reversed_string+=' '+word_list.pop()\n",
    "        \n",
    "        return reversed_string"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Test cases: \n",
    "\n",
    "1. single word e.g. 'a','word'\n",
    "2. leading and tailing space sentences e.g. ' I am childish '\n",
    "3. multiple spaces between words e.g. 'I   you'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 112,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "''"
      ]
     },
     "execution_count": 112,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "o=Solution()\n",
    "o.reverseWords(' ')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A much more concise way of doing it is to use str.split() funtion:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Solution:\n",
    "    def reverseWords(self, s):\n",
    "        return \" \".join(s.split()[::-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 115,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['I', 'am']"
      ]
     },
     "execution_count": 115,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "s='I    am '\n",
    "s.split()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 165. Compare Version Numbers"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Compare two version numbers version1 and version2.\n",
    "If version1 > version2 return 1, if version1 < version2 return -1, otherwise return 0.\n",
    "\n",
    "You may assume that the version strings are non-empty and contain only digits and the . character.\n",
    "The . character does not represent a decimal point and is used to separate number sequences.\n",
    "For instance, 2.5 is not \"two and a half\" or \"half way to version three\", it is the fifth second-level revision of the second first-level revision.\n",
    "\n",
    "Here is an example of version numbers ordering:\n",
    "\n",
    "0.1 < 1.1 < 1.2 < 13.37"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution: Naive solution: split the two string and do an elementwise comparison"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def compareVersion(self, version1, version2):\n",
    "        \"\"\"\n",
    "        :type version1: str\n",
    "        :type version2: str\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        version1=version1.split('.')\n",
    "        version2=version2.split('.')\n",
    "        for (num1,num2) in zip(version1,version2):\n",
    "            num1=int(num1)\n",
    "            num2=int(num2)\n",
    "            if num1<num2:\n",
    "                return -1\n",
    "            elif num1>num2:\n",
    "                return 1\n",
    "        if len(version1)<len(version2):\n",
    "            return -1\n",
    "        elif len(version1)>len(version2):\n",
    "            return 1\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "o=Solution()\n",
    "o.compareVersion('1.1','1')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Alternatively, "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 227. Basic Calculator II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Implement a basic calculator to evaluate a simple expression string.\n",
    "\n",
    "The expression string contains only non-negative integers, +, -, *, / operators and empty spaces . The integer division should truncate toward zero.\n",
    "\n",
    "You may assume that the given expression is always valid.\n",
    "\n",
    "Some examples:\n",
    "\n",
    "\"3+2*2\" = 7\n",
    "\n",
    "\" 3/2 \" = 1\n",
    "\n",
    "\" 3+5 / 2 \" = 5\n",
    "\n",
    "Note: Do not use the eval built-in library function."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution: We could use a stack to store the elements in the expression. \"+\" and \"-\" can be seen as sign, the digit chars are numbers. The empty spaces are skipped. \"*\" and \"/\" could be performed at priority by pop out the last stored number. We could use the string method .isdigit()."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def calculate(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        stack,sign,last_digit,last_operation,combine=[],1,0,'',False\n",
    "        for c in s:\n",
    "            if c.isdigit():\n",
    "                if not combine:\n",
    "                    stack.append(sign*int(c))\n",
    "                elif last_operation=='*':\n",
    "                    stack.append(last_digit*int(c))\n",
    "                elif last_operation=='/':\n",
    "                    stack.append(last_digit/int(c))\n",
    "                    \n",
    "            if c=='+':\n",
    "                sign=1\n",
    "                combine=False\n",
    "            if c=='-':\n",
    "                sign=-1\n",
    "                combine=False\n",
    "            if c=='*':\n",
    "                last_digit=stack.pop()\n",
    "                last_operation='*'\n",
    "                combine=True\n",
    "            if c=='/':\n",
    "                last_digit=stack.pop()\n",
    "                last_operation='/'\n",
    "                combine=True\n",
    "        return sum(stack)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Example 1: \"3+2*2\"\n",
    "\n",
    "c='3',stack=[3],sign=1,last_digit=0,last_operation='',combine=false\n",
    "c='+',stack=[3],sign=1,last_digit=0,last_operation='',combine=false\n",
    "c='2',stack=[3,2],sign=1,last_digit=0,last_operation='',combine=false\n",
    "c='*',stack=[3],sign=1,last_digit=2,last_operation='*',combine=True\n",
    "c='2',stack=[3,4],sign=1,last_digit=2,last_operation='*',combine=True\n",
    "\n",
    "Example 2: \"3-5*2\"\n",
    "\n",
    "c='3',stack=[3],sign=1,last_digit=0,last_operation='',combine=false\n",
    "c='-',stack=[3],sign=-1,last_digit=0,last_operation='',combine=false\n",
    "c='5',stack=[3,-5],sign=-1,last_digit=0,last_operation='',combine=false\n",
    "c='/',stack=[3],sign=-1,last_digit=-5,last_operation='/',combine=True\n",
    "c='2',stack=[3,-2],sign=-1,last_digit=-5,last_operation='/',combine=True"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The above solution neglect the cases when a number is represented by more than 1 char: e.g. '100'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 70,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def calculate(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        stack, last_operator, num= [],'+',0\n",
    "        for i in range(len(s)):\n",
    "            if s[i].isdigit():\n",
    "                num=10*num+int(s[i])\n",
    "            if not s[i].isdigit() and s[i]!=' ' or i==len(s)-1:\n",
    "                if last_operator=='+':\n",
    "                    stack.append(num)\n",
    "                elif last_operator=='-':\n",
    "                    stack.append(-num)\n",
    "                elif last_operator=='*':\n",
    "                    stack.append(stack.pop()*num)\n",
    "                elif last_operator=='/':\n",
    "                    tmp=stack.pop()\n",
    "                    if tmp<0:\n",
    "                        stack.append(-(abs(tmp)/num))\n",
    "                    else:\n",
    "                        stack.append(tmp/num)\n",
    "                # reinitialize number and set last_operator\n",
    "                last_operator=s[i]\n",
    "                num=0\n",
    "                \n",
    "        return sum(stack)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In this problem, it is important to consider all the corner cases:\n",
    "\n",
    "1. * and /\n",
    "2. + and -\n",
    "3. multiple digit numbers\n",
    "4. *,/,+,- combined\n",
    "5. white spaces"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Example 1: \"10*2-3/2\"\n",
    "\n",
    "stack, last_operator, num= [],'+',0\n",
    "\n",
    "* i=0: s[0]='1', num=0+1=1, stack=[], last_operator='+';\n",
    "* i=1: s[1]='0', num=10*1+0=10, stack=[], last_operator='+';\n",
    "* i=2: s[2]='*', num=0, stack=[10], last_operator='*';\n",
    "* i=3: s[3]='2', num=10*0+2=2, stack=[10], last_operator='*';\n",
    "* i=4: s[4]='-', num=0, stack=[10*2], last_operator='-';\n",
    "* i=5: s[5]='3', num=3, stack=[20], last_operator='-';\n",
    "* i=6: s[6]='/', num=0, stack=[20,-3],last_operator='/';\n",
    "* i=7: s[7]='2', num=2, stack=[20,-1],last_operator='2', num=0;\n",
    "\n",
    "Example 2: \"10*2-3/2 \"\n",
    "\n",
    "stack, last_operator, num= [],'+',0\n",
    "\n",
    "* i=0: s[0]='1', num=0+1=1, stack=[], last_operator='+';\n",
    "* i=1: s[1]='0', num=10*1+0=10, stack=[], last_operator='+';\n",
    "* i=2: s[2]='*', num=0, stack=[10], last_operator='*';\n",
    "* i=3: s[3]='2', num=10*0+2=2, stack=[10], last_operator='*';\n",
    "* i=4: s[4]='-', num=0, stack=[10*2], last_operator='-';\n",
    "* i=5: s[5]='3', num=3, stack=[20], last_operator='-';\n",
    "* i=6: s[6]='/', num=0, stack=[20,-3],last_operator='/';\n",
    "* i=7: s[7]='2', num=2, stack=[20,-3],last_operator='/';\n",
    "* i=8: s[8]=' ', num=0, stack=[20,-1],last_operator=' ';"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 344. Reverse String"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Write a function that takes a string as input and returns the string reversed.\n",
    "\n",
    "Example:\n",
    "Given s = \"hello\", return \"olleh\"."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def reverseString(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        return ''.join(s[::-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'gnirts'"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "s='string'\n",
    "s[::-1]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 345. Reverse Vowels of a String"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Write a function that takes a string as input and reverse only the vowels of a string.\n",
    "\n",
    "Example 1:\n",
    "Given s = \"hello\", return \"holle\".\n",
    "\n",
    "Example 2:\n",
    "Given s = \"leetcode\", return \"leotcede\".\n",
    "\n",
    "Note:\n",
    "The vowels does not include the letter \"y\"."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution: First we pick up the positions of the vowels in the word and store them into a list. Then we do a pivoted swap according to the position list. The algorithm will take O(n) time and O(n) space."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def reverseVowels(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        vowels_list={'a','e','i','o','u','A','E','I','O','U'}\n",
    "        s_list=list(s)\n",
    "        n=len(s_list)\n",
    "        positions=[]\n",
    "        # record positions of vowels\n",
    "        for i in range(n):\n",
    "            if s_list[i] in vowels_list:\n",
    "                positions.append(i)\n",
    "        # pivoted rotation\n",
    "        m=len(positions)\n",
    "        for i in range(m/2):\n",
    "            tmp=s_list[positions[i]]\n",
    "            s_list[positions[i]]=s_list[positions[m-1-i]]\n",
    "            s_list[positions[m-1-i]]=tmp\n",
    "        return ''.join(s_list)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'Aa'"
      ]
     },
     "execution_count": 40,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "o=Solution()\n",
    "o.reverseVowels('aA')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A neat two pointer implementation in pythonic way is given by the discussion solution:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def reverseVowels(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        vowels = {'a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U'}\n",
    "        L = list(s)\n",
    "        i = 0\n",
    "        j = len(L) - 1\n",
    "        while i < j:\n",
    "            while i < j and L[i] not in vowels:\n",
    "                i += 1\n",
    "            while j > i and L[j] not in vowels:\n",
    "                j -= 1\n",
    "            L[i], L[j] = L[j], L[i] # this line is much more elegant in swapping elements.\n",
    "            i += 1\n",
    "            j -= 1\n",
    "        return ''.join(L)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 383. Ransom Note"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Given an arbitrary ransom note string and another string containing letters from all the magazines, write a function that will return true if the ransom note can be constructed from the magazines ; otherwise, it will return false.\n",
    "\n",
    "Each letter in the magazine string can only be used once in your ransom note.\n",
    "\n",
    "Note:\n",
    "You may assume that both strings contain only lowercase letters.\n",
    "\n",
    "canConstruct(\"a\", \"b\") -> false\n",
    "\n",
    "canConstruct(\"aa\", \"ab\") -> false\n",
    "\n",
    "canConstruct(\"aa\", \"aab\") -> true\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution: We could create a hashtable initialized by magazine where the key is the char and the value is the count. Then we pass through the ransomNote to update the hashtable. \n",
    "\n",
    "1. If there is char in ransomNote that has no values in hashtable return false\n",
    "2. If the count for any char in hashtable is less than 0, return false"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 60,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def canConstruct(self, ransomNote, magazine):\n",
    "        \"\"\"\n",
    "        :type ransomNote: str\n",
    "        :type magazine: str\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        check_table={}\n",
    "        # create hashtable from magazine\n",
    "        for c in magazine:\n",
    "            if not check_table.get(c):\n",
    "                check_table[c]=1\n",
    "            else:\n",
    "                check_table[c]+=1\n",
    "        # check ransomNote\n",
    "        for c in ransomNote:\n",
    "            if not check_table.get(c):\n",
    "                return False\n",
    "            else:\n",
    "                check_table[c]-=1\n",
    "                if check_table[c]<0:\n",
    "                    return False\n",
    "                \n",
    "        return True"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The time complexity is O(len(ransomNote)+len(magazine)). The space complexity is O(len(magazine)). In python, there turns out to be a function Counter to create the hashtable and the whole problem can be solved as follows:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def canConstruct(self, ransomNote, magazine):\n",
    "    return not collections.Counter(ransomNote) - collections.Counter(magazine)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 67,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Counter({'a': 1})"
      ]
     },
     "execution_count": 67,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import collections\n",
    "collections.Counter('aa')-collections.Counter('a')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 385. <font color=red>Mini Parser"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Given a nested list of integers represented as a string, implement a parser to deserialize it.\n",
    "\n",
    "Each element is either an integer, or a list -- whose elements may also be integers or other lists.\n",
    "\n",
    "Note: You may assume that the string is well-formed:\n",
    "\n",
    "String is non-empty.\n",
    "String does not contain white spaces.\n",
    "String contains only digits 0-9, [, - ,, ].\n",
    "Example 1:\n",
    "\n",
    "Given s = \"324\",\n",
    "\n",
    "You should return a NestedInteger object which contains a single integer 324.\n",
    "Example 2:\n",
    "\n",
    "Given s = \"[123,[456,[789]]]\",\n",
    "\n",
    "Return a NestedInteger object containing a nested list with 2 elements:\n",
    "\n",
    "1. An integer containing value 123.\n",
    "2. A nested list containing two elements:\n",
    "\n",
    "    i.  An integer containing value 456.\n",
    "    \n",
    "    ii. A nested list with one element:\n",
    "         a. An integer containing value 789.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# \"\"\"\n",
    "# This is the interface that allows for creating nested lists.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class NestedInteger(object):\n",
    "#    def __init__(self, value=None):\n",
    "#        \"\"\"\n",
    "#        If value is not specified, initializes an empty list.\n",
    "#        Otherwise initializes a single integer equal to value.\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def isInteger(self):\n",
    "#        \"\"\"\n",
    "#        @return True if this NestedInteger holds a single integer, rather than a nested list.\n",
    "#        :rtype bool\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def add(self, elem):\n",
    "#        \"\"\"\n",
    "#        Set this NestedInteger to hold a nested list and adds a nested integer elem to it.\n",
    "#        :rtype void\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def setInteger(self, value):\n",
    "#        \"\"\"\n",
    "#        Set this NestedInteger to hold a single integer equal to value.\n",
    "#        :rtype void\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def getInteger(self):\n",
    "#        \"\"\"\n",
    "#        @return the single integer that this NestedInteger holds, if it holds a single integer\n",
    "#        Return None if this NestedInteger holds a nested list\n",
    "#        :rtype int\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def getList(self):\n",
    "#        \"\"\"\n",
    "#        @return the nested list that this NestedInteger holds, if it holds a nested list\n",
    "#        Return None if this NestedInteger holds a single integer\n",
    "#        :rtype List[NestedInteger]\n",
    "#        \"\"\"\n",
    "\n",
    "class Solution(object):\n",
    "    def deserialize(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: NestedInteger\n",
    "        \"\"\"\n",
    "        "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "## 459. Repeated Substring Pattern"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Given a non-empty string check if it can be constructed by taking a substring of it and appending multiple copies of the substring together. You may assume the given string consists of lowercase English letters only and its length will not exceed 10000.\n",
    "\n",
    "Example 1:\n",
    "Input: \"abab\"\n",
    "\n",
    "Output: True\n",
    "\n",
    "Explanation: It's the substring \"ab\" twice.\n",
    "\n",
    "Example 2:\n",
    "Input: \"aba\"\n",
    "\n",
    "Output: False\n",
    "\n",
    "Example 3:\n",
    "Input: \"abcabcabcabc\"\n",
    "\n",
    "Output: True\n",
    "\n",
    "Explanation: It's the substring \"abc\" four times. (And the substring \"abcabc\" twice.)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution: First solution, record substring for i in range(0,len(str)/2) and check if their repeated patter matches the full string. Time complexity O(n^2), space complexity O(n). Can we improve? If a string is repeated:\n",
    "\n",
    "str=s1s1s1s1\n",
    "\n",
    "strstr=s0s1s1s1s1s1s1s2\n",
    "\n",
    "So we could still find str in concatenated string if str is comprised of repeated substring. This search operation will be O(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def repeatedSubstringPattern(self, str):\n",
    "        \"\"\"\n",
    "        :type str: str\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        concat=str*2\n",
    "        return str in concat[1:-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[]"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a=[1]\n",
    "a[:-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "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.12"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}