Greedy algorithms look for a simple, easy-to-implement solution to complex problems. These algorithms work by recursively constructing a smaller instance of the the same problem with a rule that is easy to understand and straightforward.
The advantage is they are intuitive and efficient. The disadvantage is they often find a solutions that is far away from the optimum; i.e if you want to find the maximum of a function you could always move in the direction of the steepest gradient and you will find a local maximum. However this local maximum will often be much smaller than the global maximum.
Minimum Spanning Tree and Shortest Path are good examples for efficient greedy algorithms that find best solutions. Today I came across another problem with such an astonishing simple solution.
The Subsequence Problem
Given a string s and a string t, check if s is subsequence of t.
You may assume that there is only lower case English letters in both s and t. t is potentially a very long (length ~= 500,000) string, and s is a short string (<=100).
A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, "ace" is a subsequence of "abcde" while "aec" is not).
Solution with o(n) runtime and o(n) space: Iterating over the string s we are looking for the next character c of s in t – we skip all characters in t that are not equal to c. If we find c in t we remove c from s and remove the prefix read from t. This results in a smaller instance of the Problem that has the same result. Unwinding the recursion results in the following Swift implementation.
