Find whether a given string is formed by the .
1
/**//*Design an algorithm to find whether a given string is formed by the
2
interleaving of two given strings or not. s1= aabccabc s2= dbbabc s3= aabdbbccababcc
3Given s1,s2,s3 design an efficient algorithm to find whether s3 is formed
4from the interleaving of s1 and s2.
5
*/
6
char s1[]= "aabccabc";
7 char s2[]= "dbbabc";
8 char s3[]= "aabdbbccababcc";
9 int i1=0,i2=0,i3=0;
10
11 //这个问题在输入的s1,s2有重复时不能一次遍历就可以得到结论，而是需要遍历所有可能
12 //因此使用了回溯法
13 bool Test()
14 
{
15 if(strlen(s3)!=strlen(s1) + strlen(s2))
16 return false;
17
18 while(s3[i3] && s2[i2]==s3[i3] && s1[i1]!=s3[i3])
19
{
20 i2++;i3++;
21
}
22
23 while(s3[i3] && s2[i2]!=s3[i3] && s1[i1]==s3[i3])
24 {
25 i1++;i3++;
26 }
27
28 if(!s3[i3])//s3已经结束
29 {
30 if(s1[i1] || s2[i2])
31 return false;
32 else
33 return true;
34 }
35
36 if (!s1[i1])//s1已经结束
37 {
38 for(;s2[i2]==s3[i3] && s3[i3];i2++,i3++);
39 if(!s2[i2]==0 || !s3[i3]==0)
40 return false;
41 else
42 return true;
43 }
44
45 if (!s2[i2])//s2已经结束
46 {
47 for(;s1[i1]==s3[i3] && s3[i3];i1++,i3++);
48 if(!s1[i1]==0 || !s3[i3]==0)
49 return false;
50 else
51 return true;
52 }
53
54 if (s1[i1]==s3[i3])
55 {
56 i1++;i3++;
57 if(s1[i1]==0 && s2[i2]==0 && s3[i3]==0)
58 return true;
59 else if(Test())
60 return true;
61 i1--;i3--;
62 }
63
64 if (s2[i2]==s3[i3])
65 {
66 i2++;i3++;
67 if(s1[i1]==0 && s2[i2]==0 && s3[i3]==0)
68 return true;
69 else if(Test())
70 return true;
71 i2--;i3--;
72 }
73
74 return false;
75 }
76
/**//*Design an algorithm to find whether a given string is formed by the 2
interleaving of two given strings or not. s1= aabccabc s2= dbbabc s3= aabdbbccababcc 3
Given s1,s2,s3 design an efficient algorithm to find whether s3 is formed4
from the interleaving of s1 and s2.5
*/6
char s1[]= "aabccabc";7
char s2[]= "dbbabc";8
char s3[]= "aabdbbccababcc";9
int i1=0,i2=0,i3=0;10
11
//这个问题在输入的s1,s2有重复时不能一次遍历就可以得到结论，而是需要遍历所有可能12
//因此使用了回溯法13
bool Test()14
{15
if(strlen(s3)!=strlen(s1) + strlen(s2))16
return false;17
18
while(s3[i3] && s2[i2]==s3[i3] && s1[i1]!=s3[i3])19
{20
i2++;i3++;21
}22
23
while(s3[i3] && s2[i2]!=s3[i3] && s1[i1]==s3[i3])24
{25
i1++;i3++;26
}27
28
if(!s3[i3])//s3已经结束29
{30
if(s1[i1] || s2[i2])31
return false;32
else33
return true;34
}35
36
if (!s1[i1])//s1已经结束37
{38
for(;s2[i2]==s3[i3] && s3[i3];i2++,i3++);39
if(!s2[i2]==0 || !s3[i3]==0)40
return false;41
else42
return true;43
}44
45
if (!s2[i2])//s2已经结束46
{47
for(;s1[i1]==s3[i3] && s3[i3];i1++,i3++);48
if(!s1[i1]==0 || !s3[i3]==0)49
return false;50
else51
return true;52
}53
54
if (s1[i1]==s3[i3])55
{56
i1++;i3++;57
if(s1[i1]==0 && s2[i2]==0 && s3[i3]==0)58
return true;59
else if(Test())60
return true;61
i1--;i3--;62
}63
64
if (s2[i2]==s3[i3])65
{66
i2++;i3++;67
if(s1[i1]==0 && s2[i2]==0 && s3[i3]==0)68
return true;69
else if(Test())70
return true;71
i2--;i3--;72
}73
74
return false;75
}76
- 上一篇 总结今年一些公司的待遇 (转贴)
- 下一篇 Sad匹配产生致密的深度图.