2020-07-16_runLength-encoding.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This problem was asked by Amazon.\n",
    "\n",
    "Run-length encoding is a fast and simple method of encoding strings. The basic idea is to represent repeated successive characters as a single count and character. For example, the string \"AAAABBBCCDAA\" would be encoded as \"4A3B2C1D2A\".\n",
    "\n",
    "Implement run-length encoding and decoding. You can assume the string to be encoded have no digits and consists solely of alphabetic characters. You can assume the string to be decoded is valid."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 82,
   "metadata": {},
   "outputs": [],
   "source": [
    "def runlength_encode(string):\n",
    "    \"\"\"\n",
    "    Returns run-length encoded string.\n",
    "    @string must match \"[A-Z]*\"\n",
    "    \"\"\"\n",
    "    encodings = []\n",
    "    count = 1\n",
    "    for i in range(len(string)):\n",
    "        # append to encoding if we've reached the last character\n",
    "        # or if the next character is different to the current one.\n",
    "        if i == len(string)-1 or string[i] != string[i+1]:\n",
    "            encodings.append(str(count) + string[i])\n",
    "            count = 1\n",
    "        else:\n",
    "            count += 1\n",
    "    return ''.join(encodings)\n",
    "\n",
    "def runlength_decode(string):\n",
    "    \"\"\"\n",
    "    Returns run-length decoded string.\n",
    "    @string must match \"([0-9]+[A-Z])*\"\n",
    "    \"\"\"\n",
    "    decodings = []\n",
    "    count_digits = []\n",
    "    for i in range(len(string)):\n",
    "        if string[i].isdigit():\n",
    "            # store digit\n",
    "            count_digits.append(string[i])\n",
    "        else:\n",
    "            # compute count from stored digit sequence\n",
    "            # and append the correct number of letters.\n",
    "            count = int(''.join(count_digits))\n",
    "            count_digits = []\n",
    "            decodings.append(string[i] * count)\n",
    "    return ''.join(decodings)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [],
   "source": [
    "assert runlength_encode(\"\") == \"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {},
   "outputs": [],
   "source": [
    "assert runlength_encode(\"A\") == \"1A\" "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [],
   "source": [
    "assert runlength_encode(\"AA\") == \"2A\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [],
   "source": [
    "assert runlength_encode(\"AB\") == \"1A1B\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [],
   "source": [
    "assert runlength_encode(\"ABB\") == \"1A2B\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {},
   "outputs": [],
   "source": [
    "assert runlength_encode(\"AAAABBBCCDAA\") == \"4A3B2C1D2A\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 83,
   "metadata": {},
   "outputs": [],
   "source": [
    "assert runlength_decode(\"\") == \"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 84,
   "metadata": {},
   "outputs": [],
   "source": [
    "assert runlength_decode(\"0A0B0C\") == \"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 85,
   "metadata": {},
   "outputs": [],
   "source": [
    "assert runlength_decode(\"1A\") == \"A\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 86,
   "metadata": {},
   "outputs": [],
   "source": [
    "assert runlength_decode(\"2A\") == \"AA\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 87,
   "metadata": {},
   "outputs": [],
   "source": [
    "assert runlength_decode(\"1A1B\") == \"AB\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 88,
   "metadata": {},
   "outputs": [],
   "source": [
    "assert runlength_decode(\"1A2B\") == \"ABB\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 89,
   "metadata": {},
   "outputs": [],
   "source": [
    "assert runlength_decode(\"4A3B2C1D2A\") == \"AAAABBBCCDAA\""
   ]
  }
 ],
 "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.7.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}