字符混编
http://www.nowcoder.com/questionTerminal/0ed4ac79ab264c6f9b58fc9ba6188793
这道题有一种做法，不是很理解，求理解： 动态规划：
令D[i][j]代表A中取前i个字符，B中取前j个字符，是否和C中的前i+j个字符交错匹配。
1. 如果i==0 或者j ==
0,那么退化为单独的一个字符串是否和C匹配
因此：
D[i][0] = A(i-1) == C(i-1);
1<=i<=A.length
D[0][j] = B(j-1) == C(j-1);
1<=j<=B.length
2. 求D[i][j],分两种情况A[i-1] ==
C[i+j-1]或者B[j-1] == C[i+j-1]
D[i][j] = D[i-1][j] &&
A[i-1] == C[i+j-1]
D[i][j] = D[i][j-1] &&
B[j-1] == C[i+j-1]
因此状态转移方程：
D[i][j] = D[i-1][j] &&
A[i-1] == C[i+j-1] || D[i][j-1] && B[j-1] == C[i+j-1]
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
|
publicstaticbooleanmixture(String A,String B,String C){
intn = A.length();
intm = B.length();
intv = C.length();
if(m+n != v || v == 0){
returnfalse;
}
//C(i+j) 是否是A(1..i)和B(1..j)的交错字符串
boolean[][] D = newboolean[n+1][m+1];
for(inti = 1; i <= n; i ++){
D[i][0] = A.charAt(i-1) == C.charAt(i-1);
}
for(intj = 1; j <= m ; j ++){
D[0][j] = B.charAt(j-1) == C.charAt(j-1);
}
for(inti = 1; i <= n ; i ++ ){
for(intj = 1; j <= m ; j ++){
D[i][j] = ((A.charAt(i-1) == C.charAt(i+j-1) &&
D[i-1][j])
|| (B.charAt(j-1) == C.charAt(i+j-1) &&
D[i][j-1]));
}
}
returnD[n][m];
}
|
查看2道真题和解析
投递哔哩哔哩等公司7个岗位 >