Strings
String problems are ubiquitous and often serve as a medium to test other algorithmic patterns, such as dynamic programming, two pointers, or sliding window. Specific string algorithms also exist for more complex search and manipulation tasks.
Many string problems involving two strings can be solved with a 2D DP table, where
dp[i][j] typically stores a solution for substrings s1[0..i] and s2[0..j].Example Problems:
Longest Common SubsequenceEdit DistanceInterleaving String
Solution Spotlight: Longest Common Subsequence
This tabulation solution uses a 2D array where
dp[i][j] stores the LCS length for text1[0..i-1] and text2[0..j-1]. If characters match, the length increases by 1 from the diagonal. If not, it takes the max from the top or left cell, representing the optimal choice of excluding one character.LongestCommonSubsequence.java
Loading code syntax...