Leetcode 97: Interleave string

July 1, 2018it

Introduction

It is a hard level algorithm called interleave string. I have no idea how to learn a hard level algorithm, I just plan to spend 30 minutes time on this algorithm first. Now it is 12:46 PM, I will end the study at 1:16 PM.

Brainstorming ideas

Now it is 1:07 PM. I like to write down what I thought about in last 20 minutes.

Brute force solution - using linear scan from left to right

Check length to see if longest one is the sum of two small ones.
Count how many chars from a - z and see if the sum of each char equals to the sum of interleave string by characters.
Try to think about go from two ends of the interleave string, and find chars from the two strings to match. There is a recurrence formula.


Now it is 1:12 PM. Let me read one of solutions.

One more thinking,
"a"
"a"
"aa"

"ab"
"a"
think about short string first char position in the longer string, there are how many possible position:
length + 1, check prefix and compare to interleave string's prefix to see if there is a match.

Solution 

1:12 PM - 1:22 PM 10 minutes to study.

I just cannot believe that the dynamic programming method is very similar to Deletion distance.