Interleaving String
1Try it yourself first
Think for 20-30 minutes before you open any hint. Being stuck is where the learning happens.
Only for you, saved in this browser. After you see the approach you will compare it with your idea.2What is being asked
Can s3 be formed by interleaving s1 and s2, keeping the letter order of each?
3Hint ladder
Take one rung at a time. Stop as soon as the idea clicks.
- Hint 1If len(s1) + len(s2) != len(s3), is it possible?
- Hint 2Table can[a][b]: the first a letters of s1 and first b of s2 can form the first a + b of s3.
4The approach
Have you tried the hints? The approach is built as a path from the obvious way to the clever one.
Two decks of cards, A and B, being riffle-shuffled into one pile while each deck keeps its own order. The target pile is s3. Picture a grid: moving right means taking the next card from deck B, moving down means taking the next card from deck A. A cell is reachable if you came from above and the card taken from A matches the next letter of s3, or from the left and the card from B matches.
- The obvious way
Recursion choosing the next letter from s1 or s2: O(2^(n+m)).
- The key insight
can[0][0] = True. can[a][b] is True if (a > 0 and can[a - 1][b] and s1[a - 1] == s3[a + b - 1]) or (b > 0 and can[a][b - 1] and s2[b - 1] == s3[a + b - 1]). Answer can[len1][len2].
- The algorithm
- Wrong total length: False.
- can[0][0] = True.
- Cell: came from deck A or from deck B with a matching letter.
- Return the last cell.
Watch it run
Examples1 = "ab", s2 = "cd", s3 = "acbd"
The first letter "a" of s3 is the first card of deck A ("ab").
taken: A:a
Where people slip
- Check the lengths first; otherwise the s3 index runs out of range.
How close was your idea?
You did not write an idea, and that is fine.
Be honest with yourself. This sets your revision list.
5Code
Try writing it yourself from the steps first. Then compare.
def is_interleave(s1, s2, s3):
if len(s1) + len(s2) != len(s3):
return False
can = [[False] * (len(s2) + 1) for _ in range(len(s1) + 1)] # a cards from deck A, b from deck B
can[0][0] = True
for from_first in range(len(s1) + 1):
for from_second in range(len(s2) + 1):
next_letter = from_first + from_second - 1 # the letter of s3 just placed
if from_first > 0 and can[from_first - 1][from_second] and s1[from_first - 1] == s3[next_letter]:
can[from_first][from_second] = True
if from_second > 0 and can[from_first][from_second - 1] and s2[from_second - 1] == s3[next_letter]:
can[from_first][from_second] = True
return can[len(s1)][len(s2)]Now close this and write it again from memory, in the language you will use in the interview. Reattempt after 1 day, 7 days and about 30 days.
6Still stuck? Watch a video
Seeing someone explain it out loud can make it click. Try the video after you have read the approach above.