DP on Strings Quiz
Edit distance, longest common subsequence, and palindrome DP. Drills focus on state definitions and transitions.
Question Bank
Medium
Python
4 questions
dynamic-programming
edit-distance
algorithms
quiz
1,066 views
6
Implement Levenshtein edit distance between strings s and t with O(n * m) time and O(n * m) space.
Examples
Example 1:
Input: s = 'horse', t = 'ros'
Output: 3
Explanation: dp[i][j] = edits to convert s[:i] to t[:j]. Base: dp[0][j] = j (inserts), dp[i][0] = i (deletes). Transition picks min over insert / delete / replace, plus 1, unless characters match. Optimal: 'horse' -> 'rorse' -> 'rose' -> 'ros' (3 edits).def edit_distance(s, t):
# TODO
passImplement longest common subsequence length between s and t.
Examples
Example 1:
Input: s = 'abcde', t = 'ace'
Output: 3
Explanation: dp[i][j] = LCS length of s[:i] and t[:j]. Take dp[i - 1][j - 1] + 1 on match, else max(dp[i - 1][j], dp[i][j - 1]). 'ace' is itself a subsequence of 'abcde', so the answer is 3.def lcs(s, t):
# TODO
passTrace edit_distance("horse", "ros"). What does the final value mean, and what sequence of edits achieves it?
Implement longest_palindrome_subseq(s) using O(n^2) DP.
Examples
Example 1:
Input: s = 'bbbab'
Output: 4
Explanation: LCS of s and its reverse 'babbb' is 4 (e.g. 'bbbb'). Equivalent direct DP: dp[i][j] = LPS of s[i..j]; dp[i][j] = dp[i + 1][j - 1] + 2 if s[i] == s[j] else max(dp[i + 1][j], dp[i][j - 1]).def longest_palindrome_subseq(s):
# TODO
pass