Matching and distinct subsequences

Questions 1 to 5 of 8

1. 1. What does this program print? ``python def count_picks(s, t): n = len(t) dp = [0] * (n + 1) dp[0] = 1 for ch in s: for j in range(n, 0, -1): if ch == t[j - 1]: dp[j] += dp[j - 1] return dp[n] print(count_picks('abab', 'ab')) ``

   2346
2. 2. What does this program print? ``python def wildcard_match(s, p): m = len(s) n = len(p) dp = [[False] * (n + 1) for _ in range(m + 1)] dp[0][0] = True for j in range(1, n + 1): if p[j - 1] == '*': dp[0][j] = dp[0][j - 1] for i in range(1, m + 1): for j in range(1, n + 1): pc = p[j - 1] if pc == '*': dp[i][j] = dp[i][j - 1] or dp[i - 1][j] elif pc == '?' or pc == s[i - 1]: dp[i][j] = dp[i - 1][j - 1] return dp[m][n] print(wildcard_match('abcbd', 'a*b?d')) ``

   TrueIt prints 0FalseIt raises an IndexError
3. 3. This wildcard matcher has one wrong line. What does it return for wildcard_match('ab', 'a*')? ``python def wildcard_match(s, p): m = len(s) n = len(p) dp = [[False] * (n + 1) for _ in range(m + 1)] dp[0][0] = True for j in range(1, n + 1): if p[j - 1] == '*': dp[0][j] = dp[0][j - 1] for i in range(1, m + 1): for j in range(1, n + 1): pc = p[j - 1] if pc == '*': dp[i][j] = dp[i][j - 2] or dp[i - 1][j] elif pc == '?' or pc == s[i - 1]: dp[i][j] = dp[i - 1][j - 1] return dp[m][n] print(wildcard_match('ab', 'a*')) ``

   True, because the star matches the bFalse, because the star reads dp[i][j - 2], which skips the column for aAn IndexError, because j - 2 can be -1It prints 0 and keeps going
4. 4. The inner loop of this counter runs j from 1 upward. What does it print for aaaa and aa? ``python def count_picks(s, t): n = len(t) dp = [0] * (n + 1) dp[0] = 1 for ch in s: for j in range(1, n + 1): if ch == t[j - 1]: dp[j] += dp[j - 1] return dp[n] print(count_picks('aaaa', 'aa')) ``

   641210
5. 5. For s equal to xaxb and t equal to ab, num_distinct returns 1. Which statement explains this?

   ab is a substring of xaxb, so the single pick sits in one blockThe count is 0, because the x between a and b blocks every pickThe one pick uses position 1 for a and position 3 for b, so the letters need not sit next to each otherA substring search would also report 1, so the two methods agree here