(整理)字符串处理.
-
精品文档
五、字符串编辑距离
给定一个源字符串和目标字符串，能够对源串进行如下操作：
1.
在给定位置上插入一个字符
2.
替换任意字符
3.
删除任意字符
求通过以上操作使得源字符串和目标字符串一致的最小操作步数。
简单描述一下解该题的思想，源字符串和目标字符串分
别为
str_a
、
str_b
，二者的长度分
别为
la
、
lb
，定义
f[i,j]
为子串
str_a[0...i]
和
str_b[0...j]
的最小编辑距离，简单分析可知求得的
str_a[0...i]
和
str_b[0.
..j]
的最小编辑距离有一下三种可能：
（
1
）去
掉
str_a[0...i]
的最后一个字符跟
str_b[0...j]
匹配，则
f[i,
j]
的值等于
f[i-1,
j]+1
；
（
2
）去掉
str_b[0...
j]
的最后一个字符跟
str_a[0...i]
匹配，则
f[i,
j]
的值等于
f[i,
j-1]+1
；
（
3
）去掉
str_a[0.
..i]
和
str_b[0...j]
的最后一个字符，让二者匹配求得
f[i-1,
j-1]
，计算
f[i, j]
时要考
虑当前字符是否相等，如果
str_a[i]==str_b[j]
说明该字符不用编辑，所以
f[i,
j]
的值等
于
f[i-1, j-1]
，如果
str_a[i]!=str_b[j]
说明该字符需要编辑一次（任意修改
str_a[i]
或者
str_b[j]
即可），所以
f
[i, j]
的值等于
f[i-1,
j-1]+1
。
因为题目要求的是最小的编辑距离，所以去上面上中情况中的最小值即可，因此可以得
到递推公式：
f[i, j] = Min ( f[i-1, j]+1, f[i,
j-1]+1, f[i-1, j-1]+(str_a[i]==str_b[j] ? 0 : 1)
)
维基百科中的描述如下：
1
）递归方法
(
用到
动态规划
)
由上述的递归公式可以有以下代码：
[cpp]
view
plaincopy
1.
//
求两个字符串的编辑距离问题
2.
//
递归版本，备忘录
C[i,j]
表示<
/p>
strA[i]...strA[size_A-1]
与
strB[j]...strB[size_B-1]
的编辑距离
3.
int
editDistance_mem(
char
*strA,
int
size_A,
char
*strB,
int
size_B){
精品文档
精品文档
4.
int
**C=
new
int
*[size_A+1];
5.
fo
r
(
int
i=0;i<=size_A;i++){
6.
C[i]=
new
int
[size_B+1]();
7.
}
8.
//
初始化
9.
<
/p>
for
(
int
i=0;i<=size_A;i++){
10.
for
(
int
j=0;j<=size_B;j++)
11.
C[i][j]=INT_MAX;
12.
}
13.
int
res=EDM(C,strA,0,size_A-1,strB,0,size_B-1);
14.
//free mem
15.
f
or
(
int
i=0;i<=size_A;i++){
16.
delete
[] C[i];
17.
}
18.
delete
[] C;
19.
return
res;
20.
}
21.
int
EDM(
int
**C,
char
*strA,
int
i,
int
A_end,
char
*strB,
int
j,
int
B_end){
22.
i
f
<
br>做备忘 的编辑
(C[i][j]
//
23.
return
C[i][j];
24.
if
(i>A_end){
25.
if
(j>B_end)
26.
C[i][j]=0;
27.
else
28.
C[i][j]=B_end-j+1;
29.
}
else
if
(j>B_end){
30.
if
(i>A_end)
31.
C[i][j]=0;
32.
else
33.
C[i][j]=A_end-i+1;
34.
}
35.
else
if
(strA[i]==strB[j])
36.
C[i][j]=EDM(C,strA,i+1,A_end,strB,j+1,B_end);
精品文档
精品文档
37.
else
{
38.
int
a=EDM(C,strA,i+1,A_end,strB,j+1,B_end);
39.
int
b=EDM(C,strA,i,A_end,strB,j+1,B_end);
40.
int
c=EDM(C,strA,i+1,A_end,strB,j,B_end);
41.
C[i][j]=min(a,b,c)+1;
42.
}
43.
return
C[i][j];
44.
}
2
）矩阵标记法
递推方法（也可称为矩阵标记法），通过分析可知
可以将
f[i, j]
的计算在一个二维矩
阵中进行
，上面的递推式实际上可以看做是矩阵单元的计算递推式，只要把矩阵填满了，
f[la-1,
lb-1]
的值就是要求得最小编辑距离。代码如下：
[cpp]
view
plaincopy
1.
//
求两个字符串的编辑距离问题
2.
//
递推版本
C[i,j]
表示
strA[i]...strA[size_A-1]
与
strB[j]...strB[size_B-1]
距离
3.
int
editDistance_iter(
char
*strA,
int
size_A,
char
*strB,
int
size_B){
4.
int
**C=
new
int
*[size_A+1];
5.
fo
r
(
int
i=0;i<=size_A;i++){
6.
C[i]=
new
int
[size_B+1]();
7.
}
8.
<
/p>
for
(
int
i=size_A;i>=0;i--){
9.
f
or
(
int
j=size_B;j>=0;j--){
10.
if
(i>size_A-1){
11.
if
(j>size_B-1)
12.
C[i][j]=0;
13.
else
14.
C[i][j]=size_B-j;
精品文档
精品文档
15.
}
else
if
(j>size_B-1){
16.
if
(i>size_A-1)
17.
C[i][j]=0;
18.
else
19.
C[i][j]=size_A-i;
20.
}
else
if
(strA[i]==strB[j])
21.
C[i][j]=C[i+1][j+1];
22.
else
23.
C[i][j]=min(C[i+1][j+1],C[i+1][j],C[i][j+1])+1;
24.
}
25.
}
26.
int
res=C[0][0];
27.
//free mem
28.
f
or
(
int
i=0;i<=size_A;i++){
29.
delete
[] C[i];
30.
}
31.
delete
[] C;
32.
return
res;
33.
}
六、最长不重复子串
很好理解，即求一个串内最长的不重复子串。
1
）
使用
Hash
要求子串中的字符不能重复，判重问题首先想到的就是
hash
，寻找满足要求的子串，
最直接的方
法就是遍历每个字符起始的子串，辅助
hash
，寻求最长的不
重复子串，由于要
遍历每个子串故复杂度为
O(n^2)
，
n
为字符串的长度，辅助的空间为常数
hash[256]
。代码
如下：
[cpp]
view plaincopy
1.
/*
最长不重复子串
我们记为
LNRS */
精品文档
精品文档
2.
int
maxlen;
3.
int
maxindex;
4.
void
output(
char
* arr);
5.
/*
LNRS
基本算法
hash */
6.
char
visit[256];
7.
void
LNRS_hash(
char
* arr,
int
size)
8.
{
9.
for
(
int
i = 0; i
< size; ++i)
10.
{
11.
memset(visit,0,
sizeof
(visit)
);
12.
visit[arr[i]] = 1;
13.
for
(
int
j =
i+1; j < size; ++j)
14.
{
15.
if
(visit[arr[j]] == 0)
16.
{
17.
visit[arr[j]] = 1;
18.
}
19.
else
20.
{
21.
if
(j-i > maxlen)
22.
{
23.
maxlen = j - i;
24.
maxindex = i;
25.
}
26.
break
;
27.
}
28.
}
29.
}
30.
output(arr);
31.
}
精品文档
精品文档
2
）动态规划法
字符串的问题，很多都可以用动态规划处理，比如这里求解最长不重复子串，和前面
讨论过的最长递增子序列问题就有些类似，在
LIS
(
最长递增子序列
)
问题中，
对于当前的元
素，
要么是与前面的
LI
S
构成新的最长递增子序列，
要么就是与前面稍短的子序列构成
新的
子序列或单独构成新子序列。
这里我们采用类似的思路：
某个当前的字符，
如果它与前面的最
长不重复子串中的
字符没有重复，
那么就可以以它为结尾构成新
的最长子串；
如果有重复，
那么就与某个稍短
< br>的子串构成新的子串或者单独成一个新子串。
我们来看看下面两个例子：
1
）字符串
“abcdeab”
，第二个
a
之前的最长不重复子串是
“abcde”
< br>，
a
与最长子串中的
字符有重复
，但是它与稍短的
“bcde”
串没有重复，于是它可以与其构
成一个新的子串，之前
的最长不重复子串
“abcde”
结束；
2
）字符串
< br>“abcb”
，跟前面类似，最长串
“abc”
结束，第二个字符
b
与稍短的串
“c”
构成
新的串；
我们貌似可以总结出一些东西：
当一个最长子串结束时（即遇到
重复的字符），新的
子串的长度是与（第一个重复的字符）的下标有关的
。
于是类似
LIS
，
对于每个当前的元素，
我
们
“
回头
”
去
查询是否有与之重复的，
如没有，
则最长不重复子串长度
+1
，如有，则是与第一个重复的字符之后的串构成新的最长不重复<
/p>
子串，新串的长度便是当前元素下标与重复元素下标之差
。
可以看出这里的动态规划方法时间复杂度为
O(N^2)
，我们可以与最长递增子序列的动态规
划方案进行
对比，是一个道理的。代码如下：
[cpp]
view
plaincopy
1.
/* LNRS
动态规划求解
*/
2.
int
dp[100];
3.
void
LNRS_dp(
char
* arr,
int
size)
4.
{
5.
int
i, j;
6.
maxlen =
maxindex = 0;
7.
dp[0] = 1;
精品文档
精品文档
8.
for
(i = 1; i < size; ++i)
9.
{
10.
for
(j =
i-1; j >= 0; --j)
11.
{
12.
if
(arr[j] == arr[i])
13.
{
14.
dp[i] = i - j;
15.
break
;
16.
}
17.
}
18.
if
(j ==
-1)
19.
{
20.
dp[i] = dp[i-1] + 1;
21.
}
22.
if
(dp[i] > maxlen)
23.
{
24.
maxlen = dp[i];
25.
maxindex = i + 1 - maxlen;
26.
}
27.
}
28.
output(arr);
29.
}
3
）动态规划和
hash
< br>结合
我们发现在动态规划方法中，
每次都要
“
回头
”
去寻找重复元素的位置，
所以时间复杂
度徒增到
O(n^2)
，结合方法
1
）中的
Hash
思路，我们可以用<
/p>
hash
记录元素是否出现过，
我们当然
也可以用
hash
记录元素出现过的下
标，，这样就不必
“
回头
”
了
，而时间复杂度必
然降为
O(N)
，只不过需要一个辅助的常数空间
visit[25
6]
，这也是之前我另外一篇文章
找工
作笔试面试那些事儿
(15)---
互联网公司面试的零零种种
和多家经验
提到的的空间换时间
思路，不过一般我们的面试里面
优先考虑时间复杂度，所以这是可取的方法。
精品文档