First thing in the morning, this Sunday, labor long weekend, Julia read the book about "competitive programming. She read the book -
page 112,
6.3 String Processing with Dynamic Programming
6.3.1 string alignment - edit distance
Using Dynamic Programming, she was amazed that how good the solution is provided in the book. She read aloud the analysis and solution word by word, sentence by sentence, a few times. So enjoyable experience.
The book is detailed in the previous blog:
http://juliachencoding.blogspot.ca/2016/09/book-reading-competitive-programming.html
So, she looked up google and found the similar algorithm: Leetcode 72 - edit distance
Problem statement: (Hard)
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
b) Delete a character
c) Replace a character
No comments:
Post a Comment