Question Bank
DP on Strings Quiz
Difficulty: Medium
Edit distance, longest common subsequence, and palindrome DP. Drills focus on state definitions and transitions.
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).Implement 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.Trace 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]).