Edit Distance

sighhhhh,the question seems so clearly. why is so difficult to write down the correct answer.

Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.)

You have the following 3 operations permitted on a word:

a) Insert a character
b) Delete a character
c) Replace a character

it’s obvious that f(n) bases on f(n-1)
also we have three options.insert,delete or replace.
so the minimum is among these three .
======>
f(n) = min(f(n-1,insert),f(n-1,delete),f(n-1,replace))

now we know about how the function transfers, it’s time to look for the base case.
f(0, k) = f(k, 0) = k
f(pos1,pos2) means distance required to convert word1[:pos1] to word2[:pos2]

edit_distance

like the above pic, in order to change ab(word1) to ab(word2),there are three ways.

ab(w1)->a(w2) (insert b)   

a(w1)->a(w2) (replace when the next are not equal)

a(w1)->ab(w2)(delete b)

reference: https://www.youtube.com/watch?v=We3YDTzNXEk

solutions:

dynamic programming

dynamic programming (also known as dynamic optimization) is a method for solving a complex problem by breaking it down into a collection of simpler subproblems, solving each of those subproblems just once, and storing their solutions – ideally, using a memory-based data structure. The next time the same subproblem occurs, instead of recomputing its solution, one simply looks up the previously computed solution, thereby saving computation time at the expense of a (hopefully) modest expenditure in storage space.

The definition show us how to deal with the dynamic programming problem step by step, but why can’t i solve them easily? LOL

bottom-up dynamic programming algorithm:

1.start from the very beginning
2.use loop instead of recursive

Median of Two Sorted Arrays

There are two sorted arrays nums1 and nums2 of size m and n respectively.

Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

Example 1:

Example 2:

唉,搞咗好耐都系做唔出
#solution1
Median of Two Sorted Arrays

#solution2

Longest Substring Without Repeating Characters

Given a string, find the length of the longest substring without repeating characters.

Examples:

Given "abcabcbb", the answer is "abc", which the length is 3.

Given "bbbbb", the answer is "b", with the length of 1.

Given "pwwkew", the answer is "wke", with the length of 3. Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

longest substring without repeating characters