2060. Check if an Original String Exists Given Two Encoded Strings
Problem Description
This problem asks you to determine if two encoded strings could have originated from the same original string.
The encoding process works as follows:
- Start with an original string containing only lowercase English letters
- Split this string into a sequence of non-empty substrings (in any way you choose)
- Optionally replace some of these substrings with their lengths (as numeric strings)
- Concatenate everything together to form the encoded string
For example, the original string "abcdefghijklmnop"
could be encoded as "ab121p"
by:
- Splitting into:
["ab", "cdefghijklmn", "o", "p"]
- Replacing the 2nd and 3rd elements with their lengths:
["ab", "12", "1", "p"]
- Concatenating to get:
"ab121p"
Given two encoded strings s1
and s2
(containing lowercase letters and digits 1-9), you need to return true
if there exists some original string that could be encoded to produce both s1
and s2
. Otherwise, return false
.
The key insight is that digits in the encoded strings represent the lengths of substrings from the original. So when comparing two encoded strings, you need to account for the fact that:
- Letters must match exactly with corresponding letters
- Digits represent "wildcards" that can match any substring of the specified length
- A digit sequence like
"12"
means 12 consecutive characters from the original string
The challenge is handling all possible interpretations of digit sequences (since "12"
could mean 12 characters, or it could be "1"
and "2"
representing 1 and 2 characters respectively) and determining if there's a valid matching between the two encoded strings.
Note: The problem guarantees that no more than 3 consecutive digits appear in the encoded strings.
Intuition
The key realization is that we need to match two encoded strings character by character, but digits create flexibility since they represent "wildcards" of variable length. Think of it like having two pointers moving through s1
and s2
, but sometimes one pointer can "skip ahead" when it encounters digits.
The main challenge is handling the mismatch between positions. When s1
has a digit like "5"
, it means 5 characters from the original string, while s2
might have those same 5 characters represented as "2"
+ "3"
or as actual letters like "ab3"
. We need to track this "difference" or "delta" between how many characters each string has consumed from the original.
Consider this example: if s1 = "a3"
and s2 = "2bc"
, both could represent "abbc"
:
s1
:"a"
+ 3 chars ("bbc"
)s2
: 2 chars ("ab"
) +"b"
+"c"
The insight is to use dynamic programming with state dp[i][j][delta]
where:
i
is the current position ins1
j
is the current position ins2
delta
represents the "balance" - how many more characterss1
has consumed versuss2
When delta > 0
, s1
is "ahead" and needs s2
to catch up. When delta < 0
, s2
is ahead. When delta = 0
, both strings have consumed the same number of characters from the original string and can potentially match letters directly.
At each state, we have several transitions:
- If we see digits, we can interpret them as numbers and adjust the delta accordingly
- If
delta ≠ 0
, we can match letters against the "debt" created by previous digits - If
delta = 0
and both positions have the same letter, they can match directly
The answer is true
if we can reach dp[n][m][0]
, meaning we've processed both strings entirely and they've consumed the same total number of characters from the original string.
Learn more about Dynamic Programming patterns.
Solution Approach
The solution uses dynamic programming with a 3D state space represented as a 2D array where each cell contains a Set
of possible delta values.
State Definition:
dp[i][j]
is aSet
containing all possible delta values when we've processedi
characters froms1
andj
characters froms2
delta
represents the difference in consumed characters: positive meanss1
consumed more, negative meanss2
consumed more
Initialization:
dp[0][0].add(0)
- at the start, both strings have consumed 0 characters
State Transitions:
For each state (i, j)
with delta value, we have five possible transitions:
-
Process digits in
s1
(whendelta <= 0
):for (let p = i; p < Math.min(i + 3, n); p++) { if (isDigit(s1[p])) { num = num * 10 + Number(s1[p]); dp[p + 1][j].add(delta + num); } }
When
s1
is not ahead, we can interpret consecutive digits (up to 3) as a number and add it to delta. -
Process digits in
s2
(whendelta >= 0
):for (let q = j; q < Math.min(j + 3, m); q++) { if (isDigit(s2[q])) { num = num * 10 + Number(s2[q]); dp[i][q + 1].add(delta - num); } }
When
s2
is not ahead, we can interpret consecutive digits and subtract from delta. -
Match letter in
s1
against deficit (whendelta < 0
):if (i < n && delta < 0 && !isDigit(s1[i])) { dp[i + 1][j].add(delta + 1); }
If
s2
previously consumed more characters (negative delta), a letter ins1
can match one of those characters. -
Match letter in
s2
against surplus (whendelta > 0
):if (j < m && delta > 0 && !isDigit(s2[j])) { dp[i][j + 1].add(delta - 1); }
If
s1
previously consumed more characters (positive delta), a letter ins2
can match one of those characters. -
Direct letter matching (when
delta == 0
):if (i < n && j < m && delta == 0 && s1[i] == s2[j]) { dp[i + 1][j + 1].add(0); }
When both strings have consumed the same amount, matching letters can directly correspond.
Final Check:
Return dp[n][m].has(0)
- we need both strings fully processed with delta = 0, meaning they represent the same total length from the original string.
The algorithm efficiently explores all possible interpretations of digit sequences and letter matchings, using the delta mechanism to ensure consistency between the two encoded strings.
Ready to land your dream job?
Unlock your dream job with a 5-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's trace through a small example: s1 = "l23"
and s2 = "4e"
. These could both represent the original string "love":
s1 = "l23"
→"l"
+ 2 chars ("ov"
) + 3 chars ("e"
) → but wait, that's only 4 chars total- Let me reconsider:
s1 = "l23"
→"l"
+ 23 chars? No, that doesn't match withs2 = "4e"
Let me use a clearer example: s1 = "a3"
and s2 = "2bc"
. Both could represent "abbc"
:
s1
:"a"
+ 3 chars ("bbc"
)s2
: 2 chars ("ab"
) +"b"
+"c"
Step-by-step DP traversal:
Initialize: dp[0][0] = {0}
(both strings start at position 0 with delta 0)
From state (0, 0, delta=0):
- Process digit in
s2
at position 0:"2"
→dp[0][1] = {-2}
(s2 consumes 2 chars, s1 consumes 0) - Direct match letters:
s1[0]='a'
ands2[0]='2'
→ no match (one is digit)
From state (0, 1, delta=-2): Since delta < 0, s2 is ahead by 2 chars. We can:
- Match letter
s1[0]='a'
against deficit →dp[1][1] = {-1}
(s1 catches up by 1)
From state (1, 1, delta=-1): Since delta < 0, s2 is still ahead by 1. We can:
- Process digit
s1[1]='3'
(since delta ≤ 0) →dp[2][1] = {2}
(delta = -1 + 3 = 2)
From state (2, 1, delta=2): Since delta > 0, s1 is ahead by 2 chars. We can:
- Match letter
s2[1]='b'
against surplus →dp[2][2] = {1}
(s2 catches up by 1)
From state (2, 2, delta=1): Since delta > 0, s1 is still ahead by 1. We can:
- Match letter
s2[2]='c'
against surplus →dp[2][3] = {0}
(s2 catches up completely)
Final state (2, 3, delta=0):
We've processed all of s1
(length 2) and all of s2
(length 3) with delta=0.
Since dp[2][3]
contains 0, return true
- both strings can represent the same original string "abbc" where:
s1 = "a3"
encodes it as letter 'a' followed by 3 characterss2 = "2bc"
encodes it as 2 characters followed by letters 'b' and 'c'
Solution Implementation
1def possiblyEquals(s1: str, s2: str) -> bool:
2 """
3 Determines if two strings with wildcard numbers can possibly be equal.
4 Numbers in strings represent that many lowercase letters.
5
6 Args:
7 s1: First string containing letters and numbers
8 s2: Second string containing letters and numbers
9
10 Returns:
11 True if the strings can possibly be equal, False otherwise
12 """
13 s1_length = len(s1)
14 s2_length = len(s2)
15
16 # dp[i][j] stores set of possible delta values at position (i, j)
17 # delta represents the difference in wildcard counts between s1 and s2
18 # positive delta means s1 has more wildcards to consume
19 # negative delta means s2 has more wildcards to consume
20 dp = [[set() for _ in range(s2_length + 1)] for _ in range(s1_length + 1)]
21
22 # Initialize: at position (0, 0) with no wildcard difference
23 dp[0][0].add(0)
24
25 # Process all positions in both strings
26 for i in range(s1_length + 1):
27 for j in range(s2_length + 1):
28 # Process each possible delta value at current position
29 for delta in dp[i][j]:
30
31 # Case 1: Parse consecutive digits in s1 as a wildcard number
32 if delta <= 0:
33 wildcard_value = 0
34 # Parse up to 3 consecutive digits (max wildcard is 999)
35 for next_pos in range(i, min(i + 3, s1_length)):
36 if is_digit(s1[next_pos]):
37 wildcard_value = wildcard_value * 10 + int(s1[next_pos])
38 # Add this wildcard value to delta
39 dp[next_pos + 1][j].add(delta + wildcard_value)
40 else:
41 break # Stop if we encounter a non-digit
42
43 # Case 2: Parse consecutive digits in s2 as a wildcard number
44 if delta >= 0:
45 wildcard_value = 0
46 # Parse up to 3 consecutive digits (max wildcard is 999)
47 for next_pos in range(j, min(j + 3, s2_length)):
48 if is_digit(s2[next_pos]):
49 wildcard_value = wildcard_value * 10 + int(s2[next_pos])
50 # Subtract this wildcard value from delta
51 dp[i][next_pos + 1].add(delta - wildcard_value)
52 else:
53 break # Stop if we encounter a non-digit
54
55 # Case 3: Match a letter in s1 with pending wildcards from s2
56 if i < s1_length and delta < 0 and not is_digit(s1[i]):
57 # Consume one wildcard from s2 to match letter in s1
58 dp[i + 1][j].add(delta + 1)
59
60 # Case 4: Match a letter in s2 with pending wildcards from s1
61 if j < s2_length and delta > 0 and not is_digit(s2[j]):
62 # Consume one wildcard from s1 to match letter in s2
63 dp[i][j + 1].add(delta - 1)
64
65 # Case 5: Match two identical letters when no wildcards are pending
66 if i < s1_length and j < s2_length and delta == 0 and s1[i] == s2[j]:
67 # Both letters match, move to next position with delta = 0
68 dp[i + 1][j + 1].add(0)
69
70 # Check if we can reach the end of both strings with balanced wildcards
71 return 0 in dp[s1_length][s2_length]
72
73
74def is_digit(char: str) -> bool:
75 """
76 Checks if a character is a single digit (0-9).
77
78 Args:
79 char: Character to check
80
81 Returns:
82 True if the character is a digit, False otherwise
83 """
84 return char.isdigit()
85
1/**
2 * Determines if two strings with wildcard numbers can possibly be equal
3 * Numbers in strings represent that many lowercase letters
4 * @param s1 - First string containing letters and numbers
5 * @param s2 - Second string containing letters and numbers
6 * @return true if the strings can possibly be equal, false otherwise
7 */
8public boolean possiblyEquals(String s1, String s2) {
9 int s1Length = s1.length();
10 int s2Length = s2.length();
11
12 // dp[i][j] stores set of possible delta values at position (i, j)
13 // delta represents the difference in wildcard counts between s1 and s2
14 // positive delta means s1 has more wildcards to consume
15 // negative delta means s2 has more wildcards to consume
16 Set<Integer>[][] dp = new HashSet[s1Length + 1][s2Length + 1];
17
18 // Initialize all sets in the dp array
19 for (int i = 0; i <= s1Length; i++) {
20 for (int j = 0; j <= s2Length; j++) {
21 dp[i][j] = new HashSet<>();
22 }
23 }
24
25 // Initialize: at position (0, 0) with no wildcard difference
26 dp[0][0].add(0);
27
28 // Process all positions in both strings
29 for (int i = 0; i <= s1Length; i++) {
30 for (int j = 0; j <= s2Length; j++) {
31 // Process each possible delta value at current position
32 for (int delta : dp[i][j]) {
33
34 // Case 1: Parse consecutive digits in s1 as a wildcard number
35 if (delta <= 0) {
36 int wildcardValue = 0;
37 // Parse up to 3 consecutive digits (max wildcard is 999)
38 for (int nextPos = i; nextPos < Math.min(i + 3, s1Length); nextPos++) {
39 if (isDigit(s1.charAt(nextPos))) {
40 wildcardValue = wildcardValue * 10 + (s1.charAt(nextPos) - '0');
41 // Add this wildcard value to delta
42 dp[nextPos + 1][j].add(delta + wildcardValue);
43 } else {
44 break; // Stop if we encounter a non-digit
45 }
46 }
47 }
48
49 // Case 2: Parse consecutive digits in s2 as a wildcard number
50 if (delta >= 0) {
51 int wildcardValue = 0;
52 // Parse up to 3 consecutive digits (max wildcard is 999)
53 for (int nextPos = j; nextPos < Math.min(j + 3, s2Length); nextPos++) {
54 if (isDigit(s2.charAt(nextPos))) {
55 wildcardValue = wildcardValue * 10 + (s2.charAt(nextPos) - '0');
56 // Subtract this wildcard value from delta
57 dp[i][nextPos + 1].add(delta - wildcardValue);
58 } else {
59 break; // Stop if we encounter a non-digit
60 }
61 }
62 }
63
64 // Case 3: Match a letter in s1 with pending wildcards from s2
65 if (i < s1Length && delta < 0 && !isDigit(s1.charAt(i))) {
66 // Consume one wildcard from s2 to match letter in s1
67 dp[i + 1][j].add(delta + 1);
68 }
69
70 // Case 4: Match a letter in s2 with pending wildcards from s1
71 if (j < s2Length && delta > 0 && !isDigit(s2.charAt(j))) {
72 // Consume one wildcard from s1 to match letter in s2
73 dp[i][j + 1].add(delta - 1);
74 }
75
76 // Case 5: Match two identical letters when no wildcards are pending
77 if (i < s1Length && j < s2Length && delta == 0 && s1.charAt(i) == s2.charAt(j)) {
78 // Both letters match, move to next position with delta = 0
79 dp[i + 1][j + 1].add(0);
80 }
81 }
82 }
83 }
84
85 // Check if we can reach the end of both strings with balanced wildcards
86 return dp[s1Length][s2Length].contains(0);
87}
88
89/**
90 * Checks if a character is a single digit (0-9)
91 * @param c - Character to check
92 * @return true if the character is a digit, false otherwise
93 */
94private boolean isDigit(char c) {
95 return c >= '0' && c <= '9';
96}
97
1#include <vector>
2#include <unordered_set>
3#include <string>
4#include <algorithm>
5
6class Solution {
7public:
8 /**
9 * Determines if two strings with wildcard numbers can possibly be equal
10 * Numbers in strings represent that many lowercase letters
11 * @param s1 - First string containing letters and numbers
12 * @param s2 - Second string containing letters and numbers
13 * @returns true if the strings can possibly be equal, false otherwise
14 */
15 bool possiblyEquals(std::string s1, std::string s2) {
16 int s1Length = s1.length();
17 int s2Length = s2.length();
18
19 // dp[i][j] stores set of possible delta values at position (i, j)
20 // delta represents the difference in wildcard counts between s1 and s2
21 // positive delta means s1 has more wildcards to consume
22 // negative delta means s2 has more wildcards to consume
23 std::vector<std::vector<std::unordered_set<int>>> dp(
24 s1Length + 1,
25 std::vector<std::unordered_set<int>>(s2Length + 1)
26 );
27
28 // Initialize: at position (0, 0) with no wildcard difference
29 dp[0][0].insert(0);
30
31 // Process all positions in both strings
32 for (int i = 0; i <= s1Length; i++) {
33 for (int j = 0; j <= s2Length; j++) {
34 // Process each possible delta value at current position
35 for (int delta : dp[i][j]) {
36
37 // Case 1: Parse consecutive digits in s1 as a wildcard number
38 if (delta <= 0) {
39 int wildcardValue = 0;
40 // Parse up to 3 consecutive digits (max wildcard is 999)
41 for (int nextPos = i; nextPos < std::min(i + 3, s1Length); nextPos++) {
42 if (isDigit(s1[nextPos])) {
43 wildcardValue = wildcardValue * 10 + (s1[nextPos] - '0');
44 // Add this wildcard value to delta
45 dp[nextPos + 1][j].insert(delta + wildcardValue);
46 } else {
47 break; // Stop if we encounter a non-digit
48 }
49 }
50 }
51
52 // Case 2: Parse consecutive digits in s2 as a wildcard number
53 if (delta >= 0) {
54 int wildcardValue = 0;
55 // Parse up to 3 consecutive digits (max wildcard is 999)
56 for (int nextPos = j; nextPos < std::min(j + 3, s2Length); nextPos++) {
57 if (isDigit(s2[nextPos])) {
58 wildcardValue = wildcardValue * 10 + (s2[nextPos] - '0');
59 // Subtract this wildcard value from delta
60 dp[i][nextPos + 1].insert(delta - wildcardValue);
61 } else {
62 break; // Stop if we encounter a non-digit
63 }
64 }
65 }
66
67 // Case 3: Match a letter in s1 with pending wildcards from s2
68 if (i < s1Length && delta < 0 && !isDigit(s1[i])) {
69 // Consume one wildcard from s2 to match letter in s1
70 dp[i + 1][j].insert(delta + 1);
71 }
72
73 // Case 4: Match a letter in s2 with pending wildcards from s1
74 if (j < s2Length && delta > 0 && !isDigit(s2[j])) {
75 // Consume one wildcard from s1 to match letter in s2
76 dp[i][j + 1].insert(delta - 1);
77 }
78
79 // Case 5: Match two identical letters when no wildcards are pending
80 if (i < s1Length && j < s2Length && delta == 0 && s1[i] == s2[j]) {
81 // Both letters match, move to next position with delta = 0
82 dp[i + 1][j + 1].insert(0);
83 }
84 }
85 }
86 }
87
88 // Check if we can reach the end of both strings with balanced wildcards
89 return dp[s1Length][s2Length].count(0) > 0;
90 }
91
92private:
93 /**
94 * Checks if a character is a single digit (0-9)
95 * @param c - Character to check
96 * @returns true if the character is a digit, false otherwise
97 */
98 bool isDigit(char c) {
99 return c >= '0' && c <= '9';
100 }
101};
102
1/**
2 * Determines if two strings with wildcard numbers can possibly be equal
3 * Numbers in strings represent that many lowercase letters
4 * @param s1 - First string containing letters and numbers
5 * @param s2 - Second string containing letters and numbers
6 * @returns true if the strings can possibly be equal, false otherwise
7 */
8function possiblyEquals(s1: string, s2: string): boolean {
9 const s1Length = s1.length;
10 const s2Length = s2.length;
11
12 // dp[i][j] stores set of possible delta values at position (i, j)
13 // delta represents the difference in wildcard counts between s1 and s2
14 // positive delta means s1 has more wildcards to consume
15 // negative delta means s2 has more wildcards to consume
16 const dp: Set<number>[][] = Array.from(
17 { length: s1Length + 1 },
18 () => Array.from(
19 { length: s2Length + 1 },
20 () => new Set<number>()
21 )
22 );
23
24 // Initialize: at position (0, 0) with no wildcard difference
25 dp[0][0].add(0);
26
27 // Process all positions in both strings
28 for (let i = 0; i <= s1Length; i++) {
29 for (let j = 0; j <= s2Length; j++) {
30 // Process each possible delta value at current position
31 for (const delta of dp[i][j]) {
32
33 // Case 1: Parse consecutive digits in s1 as a wildcard number
34 if (delta <= 0) {
35 let wildcardValue = 0;
36 // Parse up to 3 consecutive digits (max wildcard is 999)
37 for (let nextPos = i; nextPos < Math.min(i + 3, s1Length); nextPos++) {
38 if (isDigit(s1[nextPos])) {
39 wildcardValue = wildcardValue * 10 + Number(s1[nextPos]);
40 // Add this wildcard value to delta
41 dp[nextPos + 1][j].add(delta + wildcardValue);
42 } else {
43 break; // Stop if we encounter a non-digit
44 }
45 }
46 }
47
48 // Case 2: Parse consecutive digits in s2 as a wildcard number
49 if (delta >= 0) {
50 let wildcardValue = 0;
51 // Parse up to 3 consecutive digits (max wildcard is 999)
52 for (let nextPos = j; nextPos < Math.min(j + 3, s2Length); nextPos++) {
53 if (isDigit(s2[nextPos])) {
54 wildcardValue = wildcardValue * 10 + Number(s2[nextPos]);
55 // Subtract this wildcard value from delta
56 dp[i][nextPos + 1].add(delta - wildcardValue);
57 } else {
58 break; // Stop if we encounter a non-digit
59 }
60 }
61 }
62
63 // Case 3: Match a letter in s1 with pending wildcards from s2
64 if (i < s1Length && delta < 0 && !isDigit(s1[i])) {
65 // Consume one wildcard from s2 to match letter in s1
66 dp[i + 1][j].add(delta + 1);
67 }
68
69 // Case 4: Match a letter in s2 with pending wildcards from s1
70 if (j < s2Length && delta > 0 && !isDigit(s2[j])) {
71 // Consume one wildcard from s1 to match letter in s2
72 dp[i][j + 1].add(delta - 1);
73 }
74
75 // Case 5: Match two identical letters when no wildcards are pending
76 if (i < s1Length && j < s2Length && delta === 0 && s1[i] === s2[j]) {
77 // Both letters match, move to next position with delta = 0
78 dp[i + 1][j + 1].add(0);
79 }
80 }
81 }
82 }
83
84 // Check if we can reach the end of both strings with balanced wildcards
85 return dp[s1Length][s2Length].has(0);
86}
87
88/**
89 * Checks if a character is a single digit (0-9)
90 * @param char - Character to check
91 * @returns true if the character is a digit, false otherwise
92 */
93function isDigit(char: string): boolean {
94 return /^\d{1}$/g.test(char);
95}
96
Time and Space Complexity
Time Complexity: O(n * m * (n + m))
The algorithm uses dynamic programming with three nested loops:
- The outer two loops iterate through positions
i
from0
ton
andj
from0
tom
, giving usO(n * m)
iterations - For each
(i, j)
position, we iterate through all values indp[i][j]
set. In the worst case, the set can containO(n + m)
different delta values because:- Delta represents the difference in "virtual positions" between the two strings
- The maximum positive delta occurs when s1 has consumed all its digits (up to
3n
in value) - The maximum negative delta occurs when s2 has consumed all its digits (up to
3m
in value) - The range of possible deltas is bounded by
O(n + m)
- Inside each delta iteration, we perform operations that take at most
O(1)
time (the inner loops for parsing digits are bounded by constant 3)
Therefore, the total time complexity is O(n * m * (n + m))
.
Space Complexity: O(n * m * (n + m))
The space is dominated by the dp
array:
- We create a 2D array of size
(n + 1) × (m + 1)
- Each cell contains a
Set
that can hold up toO(n + m)
different delta values in the worst case - Therefore, the total space complexity is
O(n * m * (n + m))
Learn more about how to find time and space complexity quickly.
Common Pitfalls
1. Incorrect Handling of Multi-Digit Numbers
Pitfall: A common mistake is treating each digit independently rather than considering all possible ways to parse consecutive digits. For example, "12" could represent:
- A single number 12 (matching 12 characters)
- Two separate numbers 1 and 2 (matching 1 and 2 characters respectively)
Why it happens: It's tempting to greedily parse digits or use a simpler approach that doesn't explore all interpretations.
Solution: The code correctly handles this by using nested loops that try all possible digit sequence lengths (up to 3):
for next_pos in range(i, min(i + 3, s1_length)):
if is_digit(s1[next_pos]):
wildcard_value = wildcard_value * 10 + int(s1[next_pos])
dp[next_pos + 1][j].add(delta + wildcard_value)
2. Misunderstanding the Delta Mechanism
Pitfall: Incorrectly interpreting what the delta value represents or when to allow certain transitions. Common errors include:
- Allowing digit parsing from s1 when delta > 0 (s1 is already ahead)
- Allowing digit parsing from s2 when delta < 0 (s2 is already ahead)
Why it happens: The delta concept is counterintuitive - it tracks the "debt" of characters that need to be matched.
Solution: The code enforces correct constraints:
- Only parse digits from s1 when
delta <= 0
(s1 is not ahead) - Only parse digits from s2 when
delta >= 0
(s2 is not ahead) - Only match letters against wildcards when there's a corresponding debt
3. Forgetting to Break on Non-Digit Characters
Pitfall: When parsing consecutive digits, forgetting to stop when encountering a letter:
# WRONG - continues even after hitting a letter
for next_pos in range(i, min(i + 3, s1_length)):
wildcard_value = wildcard_value * 10 + int(s1[next_pos])
dp[next_pos + 1][j].add(delta + wildcard_value)
Why it happens: Overlooking that digit sequences must be contiguous.
Solution: Always check if the character is a digit and break if not:
if is_digit(s1[next_pos]):
wildcard_value = wildcard_value * 10 + int(s1[next_pos])
dp[next_pos + 1][j].add(delta + wildcard_value)
else:
break # Stop parsing when we hit a non-digit
4. Using Insufficient Data Structure for DP State
Pitfall: Using a 2D boolean array dp[i][j]
instead of storing sets of possible delta values:
# WRONG - loses information about possible states
dp = [[False] * (m + 1) for _ in range(n + 1)]
Why it happens: Trying to simplify the state space without realizing that multiple delta values can lead to the same (i, j) position.
Solution: Use sets to store all possible delta values at each position:
dp = [[set() for _ in range(s2_length + 1)] for _ in range(s1_length + 1)]
5. Off-by-One Errors in Index Management
Pitfall: Incorrectly managing indices when transitioning between states, especially when parsing multi-digit numbers:
# WRONG - might access out of bounds or skip positions
for next_pos in range(i + 1, i + 4): # Should start at i, not i+1
if next_pos < s1_length and is_digit(s1[next_pos]):
...
Why it happens: Confusion about whether indices represent positions before or after consuming characters.
Solution: Carefully track that dp[i][j]
means we've consumed exactly i characters from s1 and j from s2, and update indices accordingly.
Which two pointer techniques do you use to check if a string is a palindrome?
Recommended Readings
What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution
Coding Interview Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https assets algo monster recursion jpg You first call Ben and ask
Want a Structured Path to Master System Design Too? Don’t Miss This!