# Sweet Snippet 之 字符串编辑距离

• 删除某一字符
• 增加某一字符

(这里我们不允许变更某一字符,注意一下)

C(i,j)C(i, j)C(i,j) : aaa 的(前缀)子串(长度为 iii) 与 bbb 的(前缀)子串(长度为 jjj) 的字符串编辑距离.

C(i,j)={i,if j=0j,if i=0C(i−1,j−1),if a[i]=b[j]min(C(i−1,j),C(i,j−1))+1,otherwise C(i, j) = \left\{ \begin{aligned} % &amp; 0, &amp; if \ i = 0\ and\ j = 0 \\ &amp; i, &amp; if \ j = 0 \\ &amp; j, &amp; if \ i = 0 \\ &amp; C(i - 1, j - 1), &amp; if\ a[i] = b[j] \\ &amp; min(C(i - 1, j), C(i, j - 1)) + 1, &amp; otherwise \end{aligned} \right. C(i,j)=⎩⎪⎪⎪⎪⎨⎪⎪⎪⎪⎧​​i,j,C(i−1,j−1),min(C(i−1,j),C(i,j−1))+1,​if j=0if i=0if a[i]=b[j]otherwise​

-- get key from two index
function get_key(m, n)
return m .. "_" .. n
end

function edit_dist_iter(a, b, m, n)
local edit_dist_buffer = {}

edit_dist_buffer[get_key(0, 0)] = 0

for i = 1, m do
edit_dist_buffer[get_key(i, 0)] = i
end

for i = 1, n do
edit_dist_buffer[get_key(0, i)] = i
end

for i = 1, m do
for j = 1, n do
local ac = a:sub(i, i)
local bc = b:sub(j, j)
if ac == bc then
edit_dist_buffer[get_key(i, j)] = edit_dist_buffer[get_key(i - 1, j - 1)]
else
local d1 = edit_dist_buffer[get_key(i - 1, j)]
local d2 = edit_dist_buffer[get_key(i, j - 1)]
edit_dist_buffer[get_key(i, j)] = math.min(d1, d2) + 1
end
end
end

return edit_dist_buffer[get_key(m, n)]
end

function edit_dist(a, b)
return edit_dist_iter(a, b, #a, #b)
end

-- get key from two index
function get_key(m, n)
return m .. "_" .. n
end

function edit_dist_recur(a, b, m, n, buffer)
if m <= 0 then
-- result is trivial, do not need buffer
return n
elseif n <= 0 then
-- result is trivial, do not need buffer
return m
else
local ac = a:sub(m, m)
local bc = b:sub(n, n)
if ac == bc then
local d = buffer[get_key(m - 1, n - 1)]
if d then
buffer[get_key(m, n)] = d
return d
else
local d = edit_dist_recur(a, b, m - 1, n - 1, buffer)
buffer[get_key(m, n)] = d
return d
end
else
local d1 = buffer[get_key(m - 1, n)]
if not d1 then
d1 = edit_dist_recur(a, b, m - 1, n, buffer)
end

local d2 = buffer[get_key(m, n - 1)]
if not d2 then
d2 = edit_dist_recur(a, b, m, n - 1, buffer)
end

local d = math.min(d1, d2) + 1
buffer[get_key(m, n)] = d
return d
end
end
end

function edit_dist(a, b)
-- create buffer
local edit_dist_buffer = {}
return edit_dist_recur(a, b, #a, #b, edit_dist_buffer)
end

129 篇文章22 人订阅

0 条评论

## 相关文章

28620

### AI换脸ZAO一晚，成本烧掉几百万

8月30日上午10点半左右，正在使用ZAO的用户发现，想要生成一段新的AI换脸视频，已经不是等待几秒、排队第几位的问题，而是——

57930

19310

### 【JS】336- 拆解 JavaScript 中的异步模式

JavaScript 中有很多种异步编程的方式。callback、promise、generator、async await 甚至 RxJS。我最初接触不同的异...

9930

16210

### Django实战-小程序端注销和获取状态

Django网络应用开发的5项基础核心技术包括模型（Model）的设计，URL 的设计与配置，View（视图）的编写，Template（模板）的设计和Form(...

14120

### 深度强化学习（DRL）专栏（一）

【磐创AI导读】：本篇文章是深度强化学习专栏的第一篇，讲了引言和强化学习基础知识，希望对大家有所帮助。查看上篇关于本专栏的介绍：深度强化学习（DRL）专栏开篇。...

19120

### Django实战-服务端登录验证-下

Django网络应用开发的5项基础核心技术包括模型（Model）的设计，URL 的设计与配置，View（视图）的编写，Template（模板）的设计和Form(...

12520

### 一个 WebSocket 服务器是如何开发出来的？

WebSocket 协议是为了解决 http 协议的无状态、短连接（通常是）和服务端无法主动给客户端推送数据等问题而开发的新型协议，其通信基础也是基于 TCP。...

13620

8810