{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Interleaved strings\n",
    "\n",
    "Given two strings a and b and a target c, could c be formed form some interleaving/merge of a and b?\n",
    "\n",
    "For example,\n",
    "Given:\n",
    "s1 = \"aabcc\",\n",
    "s2 = \"dbbca\",\n",
    "\n",
    "When s3 = \"aadbbcbcac\", return true.\n",
    "When s3 = \"aadbbbaccc\", return false."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "s1 = \"aabcc\"\n",
    "s2 = \"dbbca\"\n",
    "\n",
    "s3t = \"aadbbcbcac\"\n",
    "s3f = \"aadbbbaccc\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(0, ''), (1, 'a'), (2, 'aa'), (3, 'aab'), (4, 'aabc'), (5, 'aabcc')]"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "[(i, s1[:i]) for i in range(len(s1)+1)]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`dp_table[i, j]` is True if `s3[:i+j]` can be formed from interleaving `s1[:i]` and `s2[:j]`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[True, False, False, False, False, False],\n",
       " [False, False, False, False, False, False],\n",
       " [False, False, False, False, False, False],\n",
       " [False, False, False, False, False, False],\n",
       " [False, False, False, False, False, False],\n",
       " [False, False, False, False, False, False]]"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "dp_table = [[False] * (len(s1) + 1) for _ in range(len(s2) + 1)]\n",
    "dp_table[0][0] = True\n",
    "dp_table"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {
    "collapsed": false,
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{(0, 0): False,\n",
       " (0, 1): False,\n",
       " (0, 2): False,\n",
       " (0, 3): False,\n",
       " (0, 4): False,\n",
       " (0, 5): False,\n",
       " (1, 0): False,\n",
       " (1, 1): False,\n",
       " (1, 2): False,\n",
       " (1, 3): False,\n",
       " (1, 4): False,\n",
       " (1, 5): False,\n",
       " (2, 0): False,\n",
       " (2, 1): False,\n",
       " (2, 2): False,\n",
       " (2, 3): False,\n",
       " (2, 4): False,\n",
       " (2, 5): False,\n",
       " (3, 0): False,\n",
       " (3, 1): False,\n",
       " (3, 2): False,\n",
       " (3, 3): False,\n",
       " (3, 4): False,\n",
       " (3, 5): False,\n",
       " (4, 0): False,\n",
       " (4, 1): False,\n",
       " (4, 2): False,\n",
       " (4, 3): False,\n",
       " (4, 4): False,\n",
       " (4, 5): False,\n",
       " (5, 0): False,\n",
       " (5, 1): False,\n",
       " (5, 2): False,\n",
       " (5, 3): False,\n",
       " (5, 4): False,\n",
       " (5, 5): False}"
      ]
     },
     "execution_count": 24,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "dp_table = {(i, j): False\n",
    "           for i in range(len(s1)+1)\n",
    "           for j in range(len(s2)+1)}\n",
    "dp_table"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def show_table(table):\n",
    "    return '\\n'.join(\n",
    "        ' '.join(str(table[i, j])[0] for j in sorted(set([k[1] for k in table])))\n",
    "        for i in sorted(set([k[0] for k in table])))        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "F F F F F F\n",
      "F F F F F F\n",
      "F F F F F F\n",
      "F F F F F F\n",
      "F F F F F F\n",
      "F F F F F F\n"
     ]
    }
   ],
   "source": [
    "print(show_table(dp_table))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "aabcc dbbca aadbbbaccc\n",
      "aa 0 0 ! ! ! True\n",
      "s2 0 1 ! d a False\n",
      "s2 0 2 ! b a False\n",
      "s2 0 3 ! b d False\n",
      "s2 0 4 ! c b False\n",
      "s2 0 5 ! a b False\n",
      "s1 1 0 a ! a True\n",
      "xx 1 1 a d a False\n",
      "xx 1 2 a b d False\n",
      "xx 1 3 a b b False\n",
      "xx 1 4 a c b False\n",
      "xx 1 5 a a b False\n",
      "s1 2 0 a ! a True\n",
      "s2 2 1 a d d True\n",
      "s2 2 2 a b b True\n",
      "s2 2 3 a b b True\n",
      "xx 2 4 a c b False\n",
      "xx 2 5 a a a False\n",
      "s1 3 0 b ! d False\n",
      "s1 3 1 b d b True\n",
      "s2 3 2 b b b True\n",
      "s1 3 2 b b b True\n",
      "s2 3 3 b b b True\n",
      "s1 3 3 b b b True\n",
      "xx 3 4 b c a False\n",
      "xx 3 5 b a c False\n",
      "s1 4 0 c ! b False\n",
      "xx 4 1 c d b False\n",
      "xx 4 2 c b b False\n",
      "xx 4 3 c b a False\n",
      "xx 4 4 c c c False\n",
      "xx 4 5 c a c False\n",
      "s1 5 0 c ! b False\n",
      "xx 5 1 c d b False\n",
      "xx 5 2 c b a False\n",
      "xx 5 3 c b c False\n",
      "xx 5 4 c c c False\n",
      "xx 5 5 c a c False\n",
      "T F F F F F\n",
      "T F F F F F\n",
      "T T T T F F\n",
      "F T T T F F\n",
      "F F F F F F\n",
      "F F F F F F\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "{(1, 0): (0, 0, 'a', 's1'),\n",
       " (2, 0): (1, 0, 'a', 's1'),\n",
       " (2, 1): (2, 0, 'd', 's2'),\n",
       " (2, 2): (2, 1, 'b', 's2'),\n",
       " (2, 3): (2, 2, 'b', 's2'),\n",
       " (3, 1): (2, 1, 'b', 's1'),\n",
       " (3, 2): (2, 2, 'b', 's1'),\n",
       " (3, 3): (2, 3, 'b', 's1')}"
      ]
     },
     "execution_count": 39,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "s3 = s3f\n",
    "\n",
    "print(s1, s2, s3)\n",
    "\n",
    "dp_table = {(i, j): False\n",
    "           for i in range(len(s1)+1)\n",
    "           for j in range(len(s2)+1)}\n",
    "\n",
    "backpointers = {}\n",
    "\n",
    "for i in range(len(s1)+1):\n",
    "    for j in range(len(s2)+1):\n",
    "        if i == 0 and j == 0:\n",
    "            dp_table[i, j] = True\n",
    "            print('aa', i, j, '!', '!', '!', dp_table[i, j])\n",
    "        elif i == 0:\n",
    "            # extend by character from s2\n",
    "            if dp_table[i, j-1] and s2[j-1] == s3[i+j-1]:\n",
    "                dp_table[i, j] = True\n",
    "                backpointers[i, j] = (i, j-1, s2[j-1], 's2')\n",
    "            print('s2', i, j, '!', s2[j-1], s3[i+j-1], dp_table[i, j])\n",
    "        elif j == 0:\n",
    "            # extend by character from s1\n",
    "            if dp_table[i-1, j] and s1[i-1] == s3[i+j-1]:\n",
    "                dp_table[i, j] = True\n",
    "                backpointers[i, j] = (i-1, j, s1[i-1], 's1')\n",
    "            print('s1', i, j, s1[i-1], '!', s3[i+j-1], dp_table[i, j])\n",
    "        else:\n",
    "            # extend by character from s2\n",
    "            if dp_table[i, j-1] and s2[j-1] == s3[i+j-1]:\n",
    "                dp_table[i, j] = True\n",
    "                backpointers[i, j] = (i, j-1, s2[j-1], 's2')\n",
    "                print('s2', i, j, s1[i-1], s2[j-1], s3[i+j-1], dp_table[i, j])                \n",
    "            # extend by character from s1\n",
    "            if dp_table[i-1, j] and s1[i-1] == s3[i+j-1]:\n",
    "                dp_table[i, j] = True\n",
    "                backpointers[i, j] = (i-1, j, s1[i-1], 's1')                \n",
    "                print('s1', i, j, s1[i-1], s2[j-1], s3[i+j-1], dp_table[i, j])\n",
    "            if not dp_table[i, j]:\n",
    "                print('xx', i, j, s1[i-1], s2[j-1], s3[i+j-1], dp_table[i, j])\n",
    "\n",
    "print(show_table(dp_table))\n",
    "backpointers"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def is_interleave(seq1, seq2, seq3, return_backpointers=False, debug=False):\n",
    "    \"\"\"Return true if seq3 is some interleaved merge of seq1 and seq2.\n",
    "    If return_backpointers, also return the set of backpointers to\n",
    "    reconstruct the interleaving\"\"\"\n",
    "    \n",
    "    # dp_table[i, j] is True if seq3[:i+j-1] is made up of an interleaving\n",
    "    # of the first i characters of seq1 and the first j characters of seq2\n",
    "    \n",
    "    if len(seq1) + len(seq2) != len(seq3):\n",
    "        if return_backpointers:\n",
    "            return False, {}\n",
    "        else:\n",
    "            return False\n",
    "    \n",
    "    dp_table = {(i, j): False\n",
    "               for i in range(len(seq1)+1)\n",
    "               for j in range(len(seq2)+1)}\n",
    "\n",
    "    backpointers = {}\n",
    "\n",
    "    for i in range(len(seq1)+1):\n",
    "        for j in range(len(seq2)+1):\n",
    "            if i == 0 and j == 0:\n",
    "                dp_table[i, j] = True\n",
    "                if debug: print('aa', i, j, '!', '!', '!', dp_table[i, j])\n",
    "            elif i == 0:\n",
    "                # extend by character from seq2\n",
    "                if dp_table[i, j-1] and seq2[j-1] == seq3[i+j-1]:\n",
    "                    dp_table[i, j] = True\n",
    "                    backpointers[i, j] = (i, j-1, seq2[j-1], 'seq2')\n",
    "                if debug: print('seq2', i, j, '!', seq2[j-1], seq3[i+j-1], dp_table[i, j])\n",
    "            elif j == 0:\n",
    "                # extend by character from seq1\n",
    "                if dp_table[i-1, j] and seq1[i-1] == seq3[i+j-1]:\n",
    "                    dp_table[i, j] = True\n",
    "                    backpointers[i, j] = (i-1, j, seq1[i-1], 'seq1')\n",
    "                if debug: print('seq1', i, j, seq1[i-1], '!', seq3[i+j-1], dp_table[i, j])\n",
    "            else:\n",
    "                # extend by character from seq2\n",
    "                if dp_table[i, j-1] and seq2[j-1] == seq3[i+j-1]:\n",
    "                    dp_table[i, j] = True\n",
    "                    backpointers[i, j] = (i, j-1, seq2[j-1], 'seq2')\n",
    "                    if debug: print('seq2', i, j, seq1[i-1], seq2[j-1], seq3[i+j-1], dp_table[i, j])                \n",
    "                # extend by character from seq1\n",
    "                if dp_table[i-1, j] and seq1[i-1] == seq3[i+j-1]:\n",
    "                    dp_table[i, j] = True\n",
    "                    backpointers[i, j] = (i-1, j, seq1[i-1], 'seq1')                \n",
    "                    if debug: print('seq1', i, j, seq1[i-1], seq2[j-1], seq3[i+j-1], dp_table[i, j])\n",
    "                if not dp_table[i, j]:\n",
    "                    if debug: print('xx', i, j, seq1[i-1], seq2[j-1], seq3[i+j-1], dp_table[i, j])\n",
    "\n",
    "    if return_backpointers:\n",
    "        return dp_table[len(seq1), len(seq2)], backpointers\n",
    "    else:\n",
    "        return dp_table[len(seq1), len(seq2)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 50,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "is_interleave(s1, s2, s3t)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(True,\n",
       " {(1, 0): (0, 0, 'a', 'seq1'),\n",
       "  (2, 0): (1, 0, 'a', 'seq1'),\n",
       "  (2, 1): (2, 0, 'd', 'seq2'),\n",
       "  (2, 2): (2, 1, 'b', 'seq2'),\n",
       "  (2, 3): (2, 2, 'b', 'seq2'),\n",
       "  (2, 4): (2, 3, 'c', 'seq2'),\n",
       "  (3, 1): (2, 1, 'b', 'seq1'),\n",
       "  (3, 2): (2, 2, 'b', 'seq1'),\n",
       "  (3, 4): (2, 4, 'b', 'seq1'),\n",
       "  (4, 2): (3, 2, 'c', 'seq1'),\n",
       "  (4, 3): (4, 2, 'b', 'seq2'),\n",
       "  (4, 4): (3, 4, 'c', 'seq1'),\n",
       "  (4, 5): (4, 4, 'a', 'seq2'),\n",
       "  (5, 3): (4, 3, 'c', 'seq1'),\n",
       "  (5, 5): (4, 5, 'c', 'seq1')})"
      ]
     },
     "execution_count": 51,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "is_interleave(s1, s2, s3t, return_backpointers=True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 52,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "is_interleave(s1, s2, s3f)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(True,\n",
       " {(1, 0): (0, 0, 'a', 'seq1'),\n",
       "  (2, 0): (1, 0, 'a', 'seq1'),\n",
       "  (3, 0): (2, 0, 'a', 'seq1'),\n",
       "  (3, 1): (3, 0, 'b', 'seq2'),\n",
       "  (4, 1): (3, 1, 'a', 'seq1'),\n",
       "  (4, 2): (4, 1, 'b', 'seq2'),\n",
       "  (4, 3): (4, 2, 'b', 'seq2')})"
      ]
     },
     "execution_count": 54,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "is_interleave('aaaa', 'bbb', 'aaababb', return_backpointers=True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "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.5.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}