In what concerns the continuous evaluation solving exercises grade during the semester, you should submit until 23:59 of November 9th
(this exercise will still be available for submission after that deadline, but without counting towards your grade)
[to understand the context of this problem, you should read the class #05 exercise sheet]


In this problem you should submit a function as described. Inside the function do not print anything that was not asked!

[IP045] A needle in a haystack

As you managed to impress the Queen of Hearts with your swapping skills, the Dodo shuffled over, flapping his wings excitedly. He was deep in thought, and after a moment, he looked at you with wide eyes and said, "I’ve been thinking, yes, thinking a lot. What happens when we remove things, yet still find meaning?"

The Dodo continued, "Imagine a word, yes? A perfectly good word. But what if we could remove certain letters — pluck them out, one by one — yet still find another word hidden within? Fascinating, isn’t it?"

The Problem

Write a function substring(needle, haystack) that given two strings needle and haystack returns True if needle can be found as (non necessarily contiguous) substring in haystack. This is the same as saying that needle can be obtained from haystack if we remove zero or more letters from it.

Constraints

The following limits are guaranteed in all the test cases that will be given to your program:

1 ≤ |needle| ≤ 100       size of the string to look for
1 ≤ |haystack| ≤ 100       size of the string that should contain another string

Example Function Calls Example Output
print(substring("omg","oh my god"))
print(substring("abc","abracadabra"))
print(substring("my","me, myself and irene"))
print(substring("lol","lllllooooo"))
print(substring("no","yes"))
True
True
True
False
False

Introduction to Programming (CC1024)
DCC/FCUP - University of Porto