Question

Please read the following restrictions before answering the question below:

• Restrictions:

  • – Do not import any modules other than math and check.

  • – You are always allowed to define your own helper/wrapper functions. Do not use Python constructs from later modules (e.g. dictionaries, zip, anything with sets or enumerators, list comprehension, commands continue or break).

  • – Abstract list functions and recursion will not be allowed.

  • Use only the functions and methods as follows:

    • ∗ abs, len, max, min, sum, range and sorted

    • ∗ Any method or constant in the math module

    • ∗ Type casting including int(), str(), float(), bool(), list()

    • ∗ The command type()

    • ∗ Any basic arithmetic operation (including +, -, *, /, //, %, **)

    • ∗ String or list slicing and indexing as well as string or list operations using the operators above.

    • ∗ Any string or list methods including the in operator.

    • ∗ input and print as well as the formatting parameter end and method format. Note that all prompts must match exactly in order and so ensure that you do not alter these prompts.

    • ∗ Loops, specifically for and while loops.

  • – Do not mutate any passed parameters unless instructions dictate otherwise. You may mutate lists you have created however.

  • – While you may use global constants in your solutions, do not use global variables for anything other than testing.

QUESTION:

Write a function

string_clean(s)

which consumes a string s and returns a string. The returned string should be similar to the consumed string, but every time a digit appears in s, a number of characters corresponding to that digit (including the digit itself) should be removed from the returned string. For instance, string_clean("car4pent3ers") => "carts". This should be done left-to-right, and if removing one digit’s substring removes another digit, then that second digit shouldn’t be considered. For instance, string_clean("29Hello!")=> "Hello!". The string must not have any digits that would require removing a substring past the end of the string. This function should run in at worst O(n) time.

Note (and hint!): The join method of strings is O(n), where n is the length of the list, assuming each element of the list is of length O(1).

Samples:

string_clean("") => ""
string_clean("I love CS116!*!*!?") => "I love CS?" string_clean("6Hello") => ""
string_clean("I have 0 apples and 39 pears") =>

"I have 0 apples and pears"

Answer 1

Below are the screenshots of code & output:

The string_clean function has been implemented, while adhering to all the restrictions mentioned. Two pointer algorithm is used to know valid words in the given string. These words are extracted using string slicing and appended to list. Finally join method is employed to return the result string.

Below is the python code for the same:

#method string clean,uses sliding window to tokenize string

#Time complexity O(n)

def string_clean(s):

i,j=0,0#stores start and ending index of window

tokens=[]#stores tokens generated

#generating tokens - O(n)

while i<len(s):#while string isn't traversed

#string function isdigit to check if character is digit

if s[i].isdigit():

if int(s[i])==0:#if digit is 0,simply advance

i=i+1

else:

#else store the previous window

tokens.append(s[j:i])

i=j=i+int(s[i])#advance to next window

else:#if character is not digit

i=i+1# simply advance

tokens.append(s[j:])#storing last token

#using join to join the tokens - O(n)

return "".join(tokens)

#testing

print("string_clean(\"\")=>\""+string_clean("")+"\"")

print("string_clean(\"I love CS116!*!*!?\")=>\""+string_clean("I love CS116!*!*!?")+"\"")

print("string_clean(\"6Hello\")=>\""+string_clean("6Hello")+"\"")

print("string_clean(\"I have 0 apples and 39 pears\")=>\""+string_clean("I have 0 apples and 39 pears")+"\"")

print("string_clean(\"car4pent3ers\")=>\""+string_clean("car4pent3ers")+"\"")

print("string_clean(\"29Hello!\")=>\""+string_clean("29Hello!")+"\"")

Below is the python code:

 #method string clean,uses sliding window to tokenize string #Time complexity O(n) def string_clean(s): i,j=0,0#stores start and ending index of window tokens=[]#stores tokens generated #generating tokens - O(n) while i<len(s):#while string isn't traversed #string function isdigit to check if character is digit if s[i].isdigit(): if int(s[i])==0:#if digit is 0,simply advance     i=i+1 else:     #else store the previous window         tokens.append(s[j:i])   i=j=i+int(s[i])#advance to next window else:#if character is not digit  i=i+1# simply advance tokens.append(s[j:])#storing last token #using join to join the tokens - O(n) return "".join(tokens) #testing print("string_clean(\"\")=>\""+string_clean("")+"\"") print("string_clean(\"I love CS116!*!*!?\")=>\""+string_clean("I love CS116!*!*!?")+"\"") print("string_clean(\"6Hello\")=>\""+string_clean("6Hello")+"\"") print("string_clean(\"I have 0 apples and 39 pears\")=>\""+string_clean("I have 0 apples and 39 pears")+"\"") print("string_clean(\"car4pent3ers\")=>\""+string_clean("car4pent3ers")+"\"") print("string_clean(\"29Hello!\")=>\""+string_clean("29Hello!")+"\"")