Skip to content

Commit 59b8f5b

Browse files
tg123tg123
committed
commit changes to gh-pages aug 27
1 parent 8df16d7 commit 59b8f5b

File tree

2 files changed

+164
-3
lines changed

2 files changed

+164
-3
lines changed

‎_includes/_root/edit-distance/README.md

+162-2
Original file line numberDiff line numberDiff line change
@@ -1,4 +1,164 @@
1+
## [Levenshtein distance](http://en.wikipedia.org/wiki/Levenshtein_distance)
12

2-
## TODO
3-
* write down thinking
3+
This is a well known problem.
44

5+
6+
Illustrating this problem using wikipedia's example
7+
8+
Making a table like [Interleaving String](../interleaving-string)
9+
10+
```
11+
+---+---+---+---+---+---+---+---+
12+
| | * | k | i | t | t | e | n |
13+
+---+---+---+---+---+---+---+---+
14+
| * | | | | | | | |
15+
+---+---+---+---+---+---+---+---+
16+
| s | | | | | | | |
17+
+---+---+---+---+---+---+---+---+
18+
| i | | | | | | | |
19+
+---+---+---+---+---+---+---+---+
20+
| t | | | | | | | |
21+
+---+---+---+---+---+---+---+---+
22+
| t | | | | | | | |
23+
+---+---+---+---+---+---+---+---+
24+
| i | | | | | | | |
25+
+---+---+---+---+---+---+---+---+
26+
| n | | | | | | | |
27+
+---+---+---+---+---+---+---+---+
28+
| g | | | | | | | |
29+
+---+---+---+---+---+---+---+---+
30+
31+
```
32+
33+
`*` here is representing an empty string
34+
35+
each gird is the `edit distance` of `string[0..x]` and `string[0..y]`
36+
37+
First row and column girds are easy to be filled:
38+
39+
* `edit distance` of an empty string to an empty string is `0`
40+
* `edit distance` of an empty string to any string is the length of that string
41+
42+
So the table should be filled like:
43+
44+
```
45+
+---+---+---+---+---+---+---+---+
46+
| | * | k | i | t | t | e | n |
47+
+---+---+---+---+---+---+---+---+
48+
| * | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
49+
+---+---+---+---+---+---+---+---+
50+
| s | 1 | | | | | | |
51+
+---+---+---+---+---+---+---+---+
52+
| i | 2 | | | | | | |
53+
+---+---+---+---+---+---+---+---+
54+
| t | 3 | | | | | | |
55+
+---+---+---+---+---+---+---+---+
56+
| t | 4 | | | | | | |
57+
+---+---+---+---+---+---+---+---+
58+
| i | 5 | | | | | | |
59+
+---+---+---+---+---+---+---+---+
60+
| n | 6 | | | | | | |
61+
+---+---+---+---+---+---+---+---+
62+
| g | 7 | | | | | | |
63+
+---+---+---+---+---+---+---+---+
64+
65+
```
66+
67+
### what's about `k` and `s`
68+
69+
in `k`'s view
70+
71+
* Insert: cant transform to `s`
72+
* Delete: cant transform to `s`
73+
* Replace: replace `k` to `s` use `1` `edit distance`
74+
75+
in `s`'s view
76+
77+
* Insert: cant transform to `k`
78+
* Delete: cant transform to `k`
79+
* Replace: replace `s` to `k` use `1` `edit distance`
80+
81+
so the number in the gird `k` and `s` should be `1`
82+
83+
### what's about `ki` and `s` (in `ki`'s view)
84+
85+
* Insert: cant transform to `s`
86+
* Delete: delete `i` then, transform to the problem `s` and `k` we solved before. 1 + `edit distance` of `s` and `k`.
87+
* Replace and Delete: replace `k` to `s` use `1` `edit distance`, then delete `k` use `1` `edit distance`. `1 + 1 = 2`
88+
89+
90+
`Delete` and `Replace then Delete` are the same thing at last, `Replace` is just the `1` `edit distance` costed by `edit distance` of `s` and `k`.
91+
92+
In this case, we can transform the problem by deleting one char: 1 + `edit distance` of `string deleted one` and `k`
93+
94+
We can fill up the second column and row now:
95+
96+
97+
```
98+
+---+---+---+---+---+---+---+---+
99+
| | * | k | i | t | t | e | n |
100+
+---+---+---+---+---+---+---+---+
101+
| * | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
102+
+---+---+---+---+---+---+---+---+
103+
| s | 1 | 1 | 2 | 3 | 4 | 5 | 6 |
104+
+---+---+---+---+---+---+---+---+
105+
| i | 2 | 2 | | | | | |
106+
+---+---+---+---+---+---+---+---+
107+
| t | 3 | 3 | | | | | |
108+
+---+---+---+---+---+---+---+---+
109+
| t | 4 | 4 | | | | | |
110+
+---+---+---+---+---+---+---+---+
111+
| i | 5 | 5 | | | | | |
112+
+---+---+---+---+---+---+---+---+
113+
| n | 6 | 6 | | | | | |
114+
+---+---+---+---+---+---+---+---+
115+
| g | 7 | 7 | | | | | |
116+
+---+---+---+---+---+---+---+---+
117+
118+
```
119+
120+
### What if `si` and `ki`
121+
122+
Obviously, `si` and `ki` equals to the `edit distance` of `s` and `k`, because `i` are both in two strings.
123+
124+
```
125+
+---+---+---+---+---+---+---+---+
126+
| | * | k | i | t | t | e | n |
127+
+---+---+---+---+---+---+---+---+
128+
| * | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
129+
+---+---+---+---+---+---+---+---+
130+
| s | 1 | 1 | 2 | 3 | 4 | 5 | 6 |
131+
+---+---+---+---+---+---+---+---+
132+
| i | 2 | 2 | 1 | | | | |
133+
+---+---+---+---+---+---+---+---+
134+
| t | 3 | 3 | | | | | |
135+
+---+---+---+---+---+---+---+---+
136+
| t | 4 | 4 | | | | | |
137+
+---+---+---+---+---+---+---+---+
138+
| i | 5 | 5 | | | | | |
139+
+---+---+---+---+---+---+---+---+
140+
| n | 6 | 6 | | | | | |
141+
+---+---+---+---+---+---+---+---+
142+
| g | 7 | 7 | | | | | |
143+
+---+---+---+---+---+---+---+---+
144+
145+
```
146+
147+
then we can fill up the table using technology we used before.
148+
149+
150+
### More common case
151+
152+
`P[word1][word2]` is the the table,
153+
154+
so `P[i][j]` have 4 choices:
155+
156+
* `P[i - 1][j] + 1` : by deleting `word1[i]` from `word1` and convert to previous problem.
157+
* `P[i][j - 1] + 1` : by deleting `word2[j]` from `word2` and convert to previous problem.
158+
* `P[i - 1][j - 1]` : only if `word1[i] == word2[j]`
159+
* `P[i - 1][j - 1] + 1` : only if `word1[i] != word2[j]`, then replace one char `word1[i]` to `word2[j]`, then this problem is converted to `P[i - 1][j - 1]`.
160+
161+
Dont worry about `Insertion`, it is just the oppsite to `Deletion`. Just different view.
162+
163+
164+
So the work remaing is easy, find the MIN of those four is ok.

‎edit-distance/index.md

+2-1
Original file line numberDiff line numberDiff line change
@@ -1,7 +1,8 @@
11
---
22
layout: solution
33
title: Edit Distance
4-
date: 2014-07-23 02:42:48 +0800
4+
date: 2014-08-27 01:17:53 +0800
5+
eaten: true
56
---
67
{% assign leetcode_name = {{page.path | remove: '/index.md'}} %}
78
{% assign leetcode_readme = {{leetcode_name | append: '/README.md' | prepend: '_root/' }} %}

0 commit comments

Comments
 (0)