Grokking Dynamic Programming Patterns for Coding Interviews
Vote

0% completed

​

Solution: Strings Interleaving

Problem Statement

Given three strings 'm', 'n', and 'p', write a method to find out if 'p' has been formed by interleaving 'm' and 'n'. 'p' would be considered interleaving 'm' and 'n' if it contains all the letters from 'm' and 'n' and the order of letters is preserved too.

Example 1:

Input: m="abd", n="cef", p="abcdef"
Output: true
Explanation: 'p' contains all the letters from 'm' and 'n' and preserves their order too.

Example 2:

Input: m="abd", n="cef", p="adcbef"
Output: false

.....

.....

.....

Like the course? Get enrolled and start learning!
S

Shan

· 4 years ago

What is the time and space complexity for top down?

Show 1 reply
G

Gary

· 4 years ago

The brute force solution seems to be incorrect? Doesn't it return False prematurely if the first letter of p doesn't match the first letters of m and n?

If I call find_SI("abc", "def", "cabdeccf"), it returns False even though "abc" and "def" are interleaved in "cabdeccf"

Show 2 replies
R

Ray

· 4 years ago

I see a lot of "leterleaving". It's a typo right? It should be "interleaving"

Show 1 reply