[LC][UBER]Word Break.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Given a string s and a dictionary of words dict, determine if s can be segmented into a space-separated sequence of one or more dictionary words.\n",
    "\n",
    "For example, given\n",
    "s = \"leetcode\",\n",
    "dict = [\"leet\", \"code\"].\n",
    "\n",
    "Return true because \"leetcode\" can be segmented as \"leet code\".\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def wordBreak(s, wordDict):\n",
    "    \"\"\"\n",
    "    :type s: str\n",
    "    :type wordDict: Set[str]\n",
    "    :rtype: bool\n",
    "    \"\"\"\n",
    "    ok = [True]\n",
    "    for i in range(1, len(s)+1):\n",
    "        ok += any(ok[j] and s[j:i] in wordDict for j in range(i)),\n",
    "        print ok\n",
    "    return ok[-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[True, False]\n",
      "[True, False, False]\n",
      "[True, False, False, False]\n",
      "[True, False, False, False, True]\n",
      "[True, False, False, False, True, False]\n",
      "[True, False, False, False, True, False, False]\n",
      "[True, False, False, False, True, False, False, False]\n",
      "[True, False, False, False, True, False, False, False, True]\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "wordBreak('leetcode', [\"leet\", \"code\"])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The idea is the following:\n",
    "\n",
    "d is an array that contains booleans\n",
    "\n",
    "**d[i] is True if there is a word in the dictionary that ends at ith index of s AND d is also True at the beginning of the word**\n",
    "\n",
    "Example:\n",
    "\n",
    "s = \"leetcode\"\n",
    "\n",
    "words = [\"leet\", \"code\"]\n",
    "\n",
    "d[3] is True because there is \"leet\" in the dictionary that ends at 3rd index of \"leetcode\"\n",
    "\n",
    "d[7] is True because there is \"code\" in the dictionary that ends at the 7th index of \"leetcode\" AND d[3] is True\n",
    "\n",
    "The result is the last index of d."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def word_break2(s, words):\n",
    "    d = [False] * len(s)\n",
    "    for i in range(len(s)):\n",
    "        for w in words:\n",
    "            # word (tail is i) matches in dict\n",
    "            # prev tail matches or prev tail is the very beginning\n",
    "            if w == s[i-len(w)+1:i+1] and (d[i-len(w)] or i-len(w) == -1):\n",
    "                print (w, i, (i-len(w)+1), (i+1)) \n",
    "                d[i] = True\n",
    "    print d\n",
    "    return d[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "('leet', 3, 0, 4)\n",
      "('code', 7, 4, 8)\n",
      "('rocks', 12, 8, 13)\n",
      "[False, False, False, True, False, False, False, True, False, False, False, False, True]\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "word_break2('leetcoderocks', [\"rocks\", \"code\", \"leet\"])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "01\n"
     ]
    }
   ],
   "source": [
    "s = '0123456'\n",
    "print s[0:2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def wordBreak(s, words):\n",
    "    n = len(s)\n",
    "    dp = [False]*(len(s)+1)\n",
    "    dp[0] = True\n",
    "    for i in range(1, n+1):\n",
    "        for w in words:\n",
    "            if dp[i-len(w)] and w == s[i-len(w):i]:\n",
    "                dp[i] = True\n",
    "        print (i, dp)\n",
    "    return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(1, [True, False, False, False, False, False, False, False, False, False, False, False, False, False])\n",
      "(2, [True, False, False, False, False, False, False, False, False, False, False, False, False, False])\n",
      "(3, [True, False, False, False, False, False, False, False, False, False, False, False, False, False])\n",
      "(4, [True, False, False, False, True, False, False, False, False, False, False, False, False, False])\n",
      "(5, [True, False, False, False, True, False, False, False, False, False, False, False, False, False])\n",
      "(6, [True, False, False, False, True, False, False, False, False, False, False, False, False, False])\n",
      "(7, [True, False, False, False, True, False, False, False, False, False, False, False, False, False])\n",
      "(8, [True, False, False, False, True, False, False, False, True, False, False, False, False, False])\n",
      "(9, [True, False, False, False, True, False, False, False, True, False, False, False, False, False])\n",
      "(10, [True, False, False, False, True, False, False, False, True, False, False, False, False, False])\n",
      "(11, [True, False, False, False, True, False, False, False, True, False, False, False, False, False])\n",
      "(12, [True, False, False, False, True, False, False, False, True, False, False, False, False, False])\n",
      "(13, [True, False, False, False, True, False, False, False, True, False, False, False, False, True])\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "wordBreak('leetcoderocks', [\"rocks\", \"code\", \"leet\"])"
   ]
  }
 ],
 "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
}