String_Implimentations.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'cream ice loves volkan'"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Reverse the words in a string. Ex: Input = “volkan loves ice cream”  , Output = “cream ice loves volkan\"\n",
    "\n",
    "def reverse_words(a_string):\n",
    "    words = a_string.split(\" \") # makes a list\n",
    "    reversed_words = []\n",
    "    for i in range(len(words)):\n",
    "        reversed_words.insert(0, words[i])\n",
    "    return \" \".join(reversed_words)\n",
    "\n",
    "test_text = \"volkan loves ice cream\"\n",
    "reverse_words(test_text)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'cream ice loves volkan'"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Reverse the words in a string in coding interview style without using the split and join functions\n",
    "\n",
    "def rev_words(string):\n",
    "    if \" \" not in string: return [string] # if the string has one word only, return the word\n",
    "    result_list = []\n",
    "    start = 0\n",
    "    string = string + \" \" # put an empty string after each word so that the words can be split until the last one\n",
    "    for i, ch in enumerate(string):\n",
    "        if ch == \" \":\n",
    "            result_list.insert(0, string[start:i])\n",
    "            start = i + 1\n",
    "    # the result list is a list of words of the original string in reversed order\n",
    "    # combine each word \n",
    "    joined_str = \"\"\n",
    "    for i in result_list:\n",
    "        joined_str += i + \" \"\n",
    "    return joined_str[:-1] # since the last word gets an \" \" as well, remove it before returning the joined_str\n",
    "\n",
    "rev_words(\"volkan loves ice cream\")\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['but', 'btu', 'ubt', 'utb', 'tbu', 'tub']"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Permutations of a string\n",
    "\n",
    "def permutations_of_a_string(string, all_perm = None, perm_item = None):\n",
    "    if all_perm == None: all_perm = []\n",
    "    if perm_item == None: perm_item = []\n",
    "    # base case\n",
    "    if len(string) == 0: \n",
    "        all_perm.append(perm_item)\n",
    "        return\n",
    "    for i in range(len(string)): # for all items in the string\n",
    "        remaining = string[:i] + string[i+1:]\n",
    "        if remaining != None:\n",
    "            permutations_of_a_string(remaining, all_perm, perm_item + [string[i]])\n",
    "    \n",
    "    return [\"\".join(items) for items in all_perm]\n",
    "\n",
    "permutations_of_a_string(\"but\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'kasjsak'"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Finding the longest palindromic sub-string in O(n^2) time and O(1) space complexity\n",
    "\n",
    "string = \"vlkasjsakwe\"\n",
    "\n",
    "# create a function that takes a string and outputs the lpss\n",
    "def lps(string):\n",
    "    if len(string) <= 1: return string\n",
    "    longest = 0\n",
    "    for i in range(1, len(string)):\n",
    "        if len(string) % 2 == 1: # if the length is odd\n",
    "            low = i-1\n",
    "            high = i + 1\n",
    "            while low > 0 and high < len(string)-1:\n",
    "                if string[low] == string[high]:\n",
    "                    length = high - low + 1\n",
    "                    if length > longest:\n",
    "                        longest = length\n",
    "                        start = low\n",
    "                low -= 1\n",
    "                high += 1\n",
    "            \n",
    "        else: # if the length is even\n",
    "            low = i\n",
    "            hight = i + 1 \n",
    "            while low > 0 and high < len(string)-1:\n",
    "                if string[low] == string[high]:\n",
    "                    length = high - low + 1\n",
    "                    if length > longest:\n",
    "                        longest = length\n",
    "                        start = low\n",
    "                low -= 1\n",
    "                high += 1\n",
    "  \n",
    "    return string[start : start + longest]\n",
    "\n",
    "lps(string)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'vlkasjsake'"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Recursively remove adjacent duplicates from a string keeping the first of the duplicates in place\n",
    "\n",
    "string = \"vlkkasjjsake\"\n",
    "\n",
    "def remove_adj_duplicates(string):\n",
    "    if len(string) == 1: return string\n",
    "    if string[0] == string[1]:\n",
    "        return remove_adj_duplicates(string[1:])\n",
    "    else:\n",
    "        clean_text = string[0] + remove_adj_duplicates(string[1:])\n",
    "        return clean_text\n",
    "    \n",
    "remove_adj_duplicates(string) \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'ayb'"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Recursively remove duplicates from a string erasing both duplicates after each time the function is called\n",
    "# Ex: test_string = \"azxxzyb\", result : ayb\n",
    "\n",
    "def rmv_adj_duplicates(string, i):\n",
    "    if not string: return \"\"\n",
    "    if i == len(string) - 1: return string\n",
    "    if len(string) == 1: return string\n",
    "    if string[i] == string[i+1]:\n",
    "        return rmv_adj_duplicates(string[:i] + string[i+2:], i-1)\n",
    "    else:\n",
    "        return rmv_adj_duplicates(string, i+1)\n",
    "\n",
    "    \n",
    "test_string = \"azxxzyb\"\n",
    "rmv_adj_duplicates(test_string, 0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "oleeH\n"
     ]
    }
   ],
   "source": [
    "# Reverse a string\n",
    "\n",
    "def reverse_string(string):\n",
    "    rotated = \"\"\n",
    "    if len(string) <= 1: return string\n",
    "    for i in reversed(range(len(string))):\n",
    "        rotated += string[i]\n",
    "    return rotated\n",
    "    \n",
    "print(reverse_string('Heelo'))   \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Check if a string can be obtained by rotating (shifting) another string with 2 places\n",
    "# Ex: str1 = \"volkan\" can be shifted to the left as: \"anvolk\" or to the right as: \"lkanvo\"\n",
    "\n",
    "def rotate_string_with_2_char(str1, str2):\n",
    "    left_shift = str1[2:] + str1[:2]\n",
    "    right_shift = str1[-2:] + str1[:-2]\n",
    "    if left_shift == str2 or right_shift == str2:\n",
    "        return True\n",
    "    else:\n",
    "        return False\n",
    "\n",
    "str1 = \"volkan\"\n",
    "str2 = \"anvolk\"\n",
    "rotate_string_with_2_char(str1, str2)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([1., 0., 1., 1., 0., 0., 1.])"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Create an array with T and F values to show whether the tendency of the numbers in array are going up or not \n",
    "# mark T for increasing and F for decreasing in REVERSE order. If the values are the same, keep the previous tendency\n",
    "# ex: [1000, 100, 500, 50, 1, 1, 5] output [T, F, T, T, F, F, T]. Start from the last index which is default: True. \n",
    "\n",
    "import numpy as np\n",
    "def tendency(array):\n",
    "    tendency_array = np.zeros(len(array))\n",
    "    last_item = len(array) - 1\n",
    "    tendency_array[last_item] = True\n",
    "    if len(array) == 1: return total\n",
    "    for i in reversed(range(len(array)-1)):\n",
    "        if i >= 1:\n",
    "            if array[i-1] > array[i]:\n",
    "                tendency_array[i-1] = True\n",
    "            elif array[i-1] < array[i]:\n",
    "                tendency_array[i-1] = False\n",
    "            elif array[i-1] == array[i]:\n",
    "                tendency_array[i-1] = tendency_array[i]\n",
    "        if i == 0:\n",
    "            tendency_array[0] = True\n",
    "    return tendency_array\n",
    "\n",
    "test_array = [1000, 100, 500, 50, 1, 1, 5]  # up down up down down down up\n",
    "tendency(test_array)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1. 0. 0. 1. 1. 0. 0. 1.]\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "1813"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Output roman numbers to decimals \n",
    "# Strategy: Check the last letter of the roman string and add it as total value of the string. Keep moving \n",
    "# towards the beginning of the string. Keep a flag to show whether the value should be decreased or increased if \n",
    "# the same letter is seen again. If the next letter is lower, mark the flag to \"decrease\" and substract it from the \n",
    "# total but if the value is bigger than the previous one, add the value to the total, and mark the flag to \"increase\" \n",
    "\n",
    "a_dict = {'I': 1, 'V': 5, 'X' : 10, 'L': 50, 'C': 100, 'D': 500, 'M':1000}\n",
    "test_string = 'MCCMXIIV'\n",
    "\n",
    "\n",
    "import numpy as np\n",
    "def tendency(string, a_dict):\n",
    "    tendency_array = np.zeros(len(string))\n",
    "    last_item = len(string) - 1\n",
    "    tendency_array[last_item] = True\n",
    "    for i in reversed(range(len(string))):\n",
    "        if i >= 1:\n",
    "            if a_dict[string[i-1]] > a_dict[string[i]]:\n",
    "                tendency_array[i-1] = True\n",
    "            elif a_dict[string[i-1]] < a_dict[string[i]]:\n",
    "                tendency_array[i-1] = False\n",
    "            elif a_dict[string[i-1]] == a_dict[string[i]]:\n",
    "                tendency_array[i-1] = tendency_array[i]\n",
    "        if i == 0:\n",
    "            tendency_array[0] = True\n",
    "    print(tendency_array) # to view\n",
    "    return tendency_array\n",
    "\n",
    "\n",
    "def convert_roman_into_decimal(string, a_dict): # input is string for roman letters and output is the decimal number\n",
    "    tendency_array = tendency(string, a_dict)\n",
    "    total = 0\n",
    "    for i in range(len(string)):\n",
    "        item_val = a_dict[string[i]]\n",
    "        if tendency_array[i] == True:\n",
    "            total += item_val\n",
    "        else:\n",
    "            total -= item_val\n",
    "\n",
    "    return total\n",
    "\n",
    "\n",
    "convert_roman_into_decimal(test_string, a_dict)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1. 0. 0. 1. 1. 0. 0. 1.]\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "1813"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Alternative solution to the problem above\n",
    "\n",
    "def roman_to_decimal(string):\n",
    "    if len(string) == 0: return None\n",
    "    last_letter = string[-1]\n",
    "    value_of_the_last_letter = a_dict[last_letter]\n",
    "    total = value_of_the_last_letter\n",
    "    memory = np.zeros(len(string))\n",
    "    memory[-1] = True\n",
    "    for i in reversed(range(1, len(string))):\n",
    "        curr_index = i\n",
    "        curr_roman_text = string[curr_index]\n",
    "        value_curr_roman_text = a_dict[curr_roman_text]\n",
    "        next_index = i-1\n",
    "        next_roman_text = string[next_index]\n",
    "        value_of_next_roman_text = a_dict[next_roman_text]\n",
    "        if value_of_next_roman_text > value_curr_roman_text:\n",
    "            total += value_of_next_roman_text\n",
    "            memory[next_index] = True\n",
    "        elif value_of_next_roman_text < value_curr_roman_text:\n",
    "            total -= value_of_next_roman_text\n",
    "            memory[next_index] = False\n",
    "        else:\n",
    "            memory[next_index] = memory[curr_index]\n",
    "            if memory[next_index] == True:\n",
    "                total += value_of_next_roman_text\n",
    "            else:\n",
    "                total -= value_of_next_roman_text\n",
    "    print(memory)            \n",
    "    return total\n",
    "\n",
    "test_string = 'MCCMXIIV' #:1813\n",
    "roman_to_decimal(test_string)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['abc', 'acb', 'bac', 'bca', 'cab', 'cba']"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Write a function that outputs the anagram of a text\n",
    "\n",
    "def anagram(text, results = None, solutions = None): \n",
    "    if results == None: results = []\n",
    "    if solutions == None: solutions = []\n",
    "    if len(text) == 0: \n",
    "        results.append(solutions)\n",
    "        return\n",
    "    for i, n in enumerate(text):\n",
    "        remaining = text[:i] + text[i+1:]\n",
    "        if remaining != None:\n",
    "            anagram(remaining, results, solutions + [n])\n",
    "    return [''.join(i) for i in results]\n",
    "\n",
    "test_text = 'abc'\n",
    "test_set = list(test_text)\n",
    "anagram(test_set)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[2, 3, 5, 26, 243, 545, 234, 4, 25, 6]\n",
      "['a', 'k', 'd', 'f', 'j', 'l', 's']\n",
      "{'j', 'l', 'd', 'f', 'k', 'a', 's'}\n",
      "dict_keys(['a', 'k', 'd', 'f', 'j', 'l', 's'])\n"
     ]
    }
   ],
   "source": [
    "# Remove duplicates in an array or string in 3 different ways, using list comprehension, set, and dictionary.\n",
    "\n",
    "# OPTION !:\n",
    "messy_array = [2,3,5,26,243,545,234,2,4,25,4,6,6,5]\n",
    "remove_duplicates_of_array = [n for i,n in enumerate(messy_array) if n not in messy_array[:i]]\n",
    "print(remove_duplicates_of_array)\n",
    "\n",
    "messy_text = 'akdfjaklfakfkasfjkalsjflasjdf'\n",
    "messy_text = list(messy_text)\n",
    "remove_duplicates_of_string = [n for i,n in enumerate(messy_text) if n not in messy_text[:i]]\n",
    "print(remove_duplicates_of_string)\n",
    "\n",
    "# OPTION 2:\n",
    "set_of_text = set(messy_text)\n",
    "print(set_of_text)\n",
    "\n",
    "\n",
    "# OPTION 3:\n",
    "a_dict = {}\n",
    "for i in range(len(messy_text)):\n",
    "    if messy_text[i] in a_dict:\n",
    "        continue\n",
    "    else:\n",
    "        a_dict[messy_text[i]] = 'True'    \n",
    "print(a_dict.keys())\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[0 1 2 2]\n",
      " [0 0 1 1]\n",
      " [0 0 0 0]\n",
      " [0 0 0 0]]\n",
      "2\n"
     ]
    }
   ],
   "source": [
    "# Write a dynamic programming based program to find minimum number insertions (addition) needed to make a palindrome \n",
    "\n",
    "# Examples:\n",
    "# ab: Number of insertions required is 1 i.e. bab    aa: Number of insertions required is 0 i.e. aa\n",
    "# abcd: Number of insertions required is 3 i.e. dcb + abcd\n",
    "\n",
    "# Algorithm:\n",
    "# The table should be filled in diagonal fashion. For the string abcde, 0….4, \n",
    "# the following should be order in which the table is filled:\n",
    "\n",
    "# Gap = 1: (0, 1) (1, 2) (2, 3) (3, 4)  --> l, h values\n",
    "# Gap = 2: (0, 2) (1, 3) (2, 4)\n",
    "# Gap = 3: (0, 3) (1, 4)\n",
    "# Gap = 4: (0, 4)\n",
    "\n",
    "import numpy as np\n",
    "\n",
    "def min_insertions_for_palindrome(str1): # look for similar letters at the edges and calculate the steps needed to make it similar\n",
    "    n = len(str1)\n",
    "    # Create a table of size n*n to store minimum number of insertions  \n",
    "    # needed to convert str1[l..h] to a palindrome. Fill the table diagonally\n",
    "    table = np.zeros([n,n], dtype = int)\n",
    "    for gap in range(1, n): \n",
    "        l = 0\n",
    "        for h in range(gap, n): \n",
    "            # if the beginning and ending letters are the same, move one index towards inner part of the string\n",
    "            # Ex iovoi then the next step is to check ovo\n",
    "            if str1[l] == str1[h]: \n",
    "                table[l][h] = table[l + 1][h - 1] \n",
    "            # if the letters at both edges are not the same, look for either moving from one side or the other\n",
    "            # find the minimum and add one more step\n",
    "            else: \n",
    "                table[l][h] = (min(table[l][h - 1], table[l + 1][h]) + 1) \n",
    "            l += 1\n",
    "    \n",
    "    print(table)\n",
    "    # Return minimum number of insertions for str1[0..n-1] \n",
    "    return table[0][n - 1]; \n",
    "  \n",
    "# Driver Code \n",
    "test_str = \"voii\"\n",
    "print(min_insertions_for_palindrome(test_str)) \n",
    "  \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[0 1 3 5]\n",
      " [0 0 2 4]\n",
      " [0 0 0 3]\n",
      " [0 0 0 0]]\n"
     ]
    }
   ],
   "source": [
    "# Reminder for diagonal insertion order to a table\n",
    "\n",
    "n = 4\n",
    "table = np.zeros([n,n], dtype = int)\n",
    "for gap in range(1, n):\n",
    "    i = 0\n",
    "    for j in range(gap, n):\n",
    "        table[i,j] = j + gap - 1 \n",
    "        i += 1\n",
    "        \n",
    "print(table)     "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'akoern'"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Find the length of the longest substring without repeating characters by using a sliding window method\n",
    "\n",
    "def longest_substr_with_dist_chars(s):\n",
    "    window = set()\n",
    "    left = 0 \n",
    "    max_length = 0\n",
    "    for right in range(len(s)):\n",
    "        while s[right] in window:# if the new element on the right is already in the window, \n",
    "            # take off all the previous elements until there is no common element left: Ex: remove: abc from abcdefgc\n",
    "            window.remove(s[left])\n",
    "            left += 1\n",
    "        window.add(s[right])\n",
    "        if len(window) > max_length:\n",
    "            max_length = len(window)\n",
    "            start_index = left\n",
    "    lcs_with_dist = s[start_index : start_index + max_length]\n",
    "    return lcs_with_dist\n",
    "    \n",
    "string = \"kakoernejf\"\n",
    "longest_substr_with_dist_chars(string)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'akoern'"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# An alternative approach to find the length of the longest substring without repeating characters \n",
    "\n",
    "import numpy as np\n",
    "def longest_substring_with_dist_chars(string):\n",
    "    n = len(string)\n",
    "    max_length = 0\n",
    "    for i in range(0, n):\n",
    "        for j in range(i, n):\n",
    "            seen_letters = string[i:j+1]\n",
    "            if len(string[i:j+1]) == len(set(string[i:j+1])):\n",
    "                length = j-i\n",
    "                if length > max_length:\n",
    "                    max_length = length\n",
    "                    mark_start_ind = i\n",
    "                    mark_end_ind = j\n",
    "                    \n",
    "    lcs = string[mark_start_ind : mark_end_ind + 1]          \n",
    "    return lcs\n",
    "\n",
    "string = \"kakoernejf\"\n",
    "longest_substring_with_dist_chars(string)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[0 0 0 0 0 0 0 0 0 0]\n",
      " [0 1 0 0 0 0 0 0 0 0]\n",
      " [0 0 0 1 0 0 1 0 0 0]\n",
      " [0 0 0 0 0 0 0 0 0 0]\n",
      " [0 0 0 0 0 0 0 0 0 1]\n",
      " [0 0 1 0 0 0 0 0 0 0]\n",
      " [0 0 0 2 0 0 1 0 0 0]\n",
      " [0 0 0 0 3 0 0 0 1 0]\n",
      " [0 0 0 0 0 4 0 0 0 0]\n",
      " [0 0 0 0 0 0 0 0 0 1]]\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "['faoi']"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Dynamic Programming Solution to longest common substring of two strings problem\n",
    "\n",
    "import numpy as np\n",
    "X = 'qalkfaoik'\n",
    "Y = 'qfaoianok'\n",
    "\n",
    "def LCsubstring(x, y):\n",
    "    n = len(x)\n",
    "    m = len(y)\n",
    "    # create a 2D known list to store the sub-solutions\n",
    "    known_list = np.zeros([n+1, m+1], dtype = int)\n",
    "    # create a list to return the solution\n",
    "    lcs = []\n",
    "    # set a variable to find the maximum length\n",
    "    longest = 0\n",
    "    # loop over the rows \n",
    "    for i in range(1, n+1):\n",
    "        # loop over the columns\n",
    "        for j in range(1, m+1):\n",
    "            # if there is a match, move down one step diagonally on the matrix and increase the value by one\n",
    "            if x[i-1] == y[j-1]:\n",
    "                known_list[i][j] = known_list[i-1][j-1] + 1\n",
    "                c = known_list[i][j]\n",
    "                if c > longest: # if it is the longest substring\n",
    "                    longest = c\n",
    "                    lcs = []\n",
    "                    lcs.append(x[i-longest: i])\n",
    "\n",
    "    print(known_list)\n",
    "    return lcs            \n",
    "            \n",
    "LCsubstring(X,Y)          "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "291"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Make an atoi() function with python \n",
    "# atoi in C language takes a string (which represents an integer) as an argument and returns its value of type int.\n",
    "\n",
    "def atoi(string): \n",
    "    total = 0\n",
    "    for i in range(0, len(string)): \n",
    "        number = (ord(string[i]) - ord('0')) # simply the string is changed to integer\n",
    "        # position of the number in decimal system\n",
    "        pos = 10**(len(string)-i-1) \n",
    "        # position * number is its current value in decimal system\n",
    "        total += number * pos\n",
    "    return total\n",
    "atoi('291')\n",
    "  \n",
    "# atoi in python is simply: int(string)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "fja\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Implement strstr function. Find the starting index of substring within a string (or its first occurence)\n",
    "# if substring is not found return -1\n",
    "\n",
    "def strstr(string, substr):\n",
    "    if len(substr) > len(string) : return\n",
    "    n = len(substr)\n",
    "    for i in range(len(string)-n):\n",
    "        if string[i:i+n] == substr:\n",
    "            print(string[i:i+n])\n",
    "            return i\n",
    "    return -1\n",
    "\n",
    "strstr('ayfjasf', 'fja')\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'hel'"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Write a function that outputs the Longest Common Prefix of multiple strings\n",
    "# Example:  if input: 'flower', 'flow', 'floight' the output is: \"flo\"\n",
    "    \n",
    "def longest_common_prefix(*args):\n",
    "    # loop over the elements of the first word\n",
    "    for i in range(len(args[0])):\n",
    "        # loop over all the elements in args\n",
    "        for j in range(1, len(args)):\n",
    "            # if the index at the first word is not seen in other words in the same place, \n",
    "            # return the previous elements\n",
    "            # if the length of any word is equal to the first word, return the previous elements as well.\n",
    "            if args[0][i] != args[j][i] or len(args[j]) == i:\n",
    "                return args[0][:i]\n",
    "longest_common_prefix('hela', 'hello', 'helicopter')    \n",
    " "
   ]
  }
 ],
 "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.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}