* Notice that the coordinates here are 1-indexed. * * @param street Karel's starting street number. * @param avenue Karel's starting avenue number. * @return The number of paths back to (1, 1) moving only left and down. */ int numPathsHome(int street, int avenue) { /* If Karel is at position (1, 1), there is one path back: just don't move anywhere! */ if (street == 1 && avenue == 1) return 1; /* If Karel is at a street or avenue numbered less than one, then just by moving left * or down there's no way to get to (1, 1). */ if (street <= 0 || avenue <= 0) return 0; /* Otherwise, every journey begins with a single step! Count how many ways we can go * home starting with a left step and hwo many ways we can go home starting with a * down step. */ return numPathsHome(street - 1, avenue) + numPathsHome(street, avenue - 1); } /** * Given two strings, returns whether the second is a subsequence of * the first. * * @param text The larger text. * @param subseq The subsequence to search for. * @return Whether text has subseq as a subsequence. */ bool hasSubsequence(const string& text, const string& subseq) { /* The empty string is a subsequence of any text string. */ if (subseq == "") return true; /* If the sequence is nonempty but the text is empty, then the sequence isn't a * subsequence of the text. */ if (text == "") return false; /* If the first characters of the text and subsequence match, then peel both off * and see whether the remaining sequence is a subsequence of the remaining text. */ if (text[0] == subseq[0]) return hasSubsequence(text.substr(1), subseq.substr(1)); /* Otherwise, they don't match. Then the sequence is a subsequence precisely if * it's a subsequence of the rest of the text. */ return hasSubsequence(text.substr(1), subseq); }