FazBrowse GitHub Viewer
|
Trending
|
URL:
|
Home
Tools:
[Download Repo ZIP]
[View Raw Code]
[Original HTTPS Page]
python-algorithms/algorithms/strings/min_distance.py at master · ilyvsc/python-algorithms · GitHub
ilyvsc
/
python-algorithms
Public
forked from
keon/algorithms
Notifications
You must be signed in to change notification settings
Fork
0
Star
1
Code
Pull requests
0
Actions
Projects
Security and quality
0
Insights
Additional navigation options
Code
Pull requests
Actions
Projects
Security and quality
Insights
Expand file tree
Breadcrumbs
python-algorithms
/
algorithms
/
strings
/
min_distance.py
Copy path
More file actions
More file actions
Latest commit
History
History
History
62 lines (52 loc) · 1.8 KB
Breadcrumbs
python-algorithms
/
algorithms
/
strings
/
min_distance.py
Copy path
File metadata and controls
62 lines (52 loc) · 1.8 KB
Raw
Copy raw file
Download raw file
Open symbols panel
Edit and raw actions
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
"""
Given two words word1 and word2, find the minimum number of steps required to
make word1 and word2 the same, where in each step you can delete one character
in either string.
For example:
Input: "sea", "eat"
Output: 2
Explanation: You need one step to make "sea" to "ea" and another step to make "eat" to "ea".
Reference: https://leetcode.com/problems/delete-operation-for-two-strings/description/
"""
def
min_distance
(
word1
,
word2
):
"""
Finds minimum distance by getting longest common subsequence
:type word1: str
:type word2: str
:rtype: int
"""
return
len
(
word1
)
+
len
(
word2
)
-
2
*
lcs
(
word1
,
word2
,
len
(
word1
),
len
(
word2
))
def
lcs
(
word1
,
word2
,
i
,
j
):
"""
The length of longest common subsequence among the two given strings word1 and word2
"""
if
i
==
0
or
j
==
0
:
return
0
if
word1
[
i
-
1
]
==
word2
[
j
-
1
]:
return
1
+
lcs
(
word1
,
word2
,
i
-
1
,
j
-
1
)
return
max
(
lcs
(
word1
,
word2
,
i
-
1
,
j
),
lcs
(
word1
,
word2
,
i
,
j
-
1
))
def
min_distance_dp
(
word1
,
word2
):
"""
Finds minimum distance in a dynamic programming manner
TC: O(length1*length2), SC: O(length1*length2)
:type word1: str
:type word2: str
:rtype: int
"""
length1
,
length2
=
len
(
word1
)
+
1
,
len
(
word2
)
+
1
res
=
[[
0
for
_
in
range
(
length2
)]
for
_
in
range
(
length1
)]
if
length1
==
length2
:
for
i
in
range
(
1
,
length1
):
res
[
i
][
0
],
res
[
0
][
i
]
=
i
,
i
else
:
for
i
in
range
(
length1
):
res
[
i
][
0
]
=
i
for
i
in
range
(
length2
):
res
[
0
][
i
]
=
i
for
i
in
range
(
1
,
length1
):
for
j
in
range
(
1
,
length2
):
if
word1
[
i
-
1
]
==
word2
[
j
-
1
]:
res
[
i
][
j
]
=
res
[
i
-
1
][
j
-
1
]
else
:
res
[
i
][
j
]
=
min
(
res
[
i
-
1
][
j
],
res
[
i
][
j
-
1
])
+
1
return
res
[
len
(
word1
)][
len
(
word2
)]
Back
|
FazBrowse Home
|
New Git URL