当前位置: 代码迷 >> 综合 >> POJ2192 Zipper(DP||DFS)
  详细解决方案

POJ2192 Zipper(DP||DFS)

热度:19   发布时间:2024-01-16 14:01:39.0

题意:

输入三个字符串,看前两个字符串能否组成第三个字符串,要求前两个字符串各自的字母顺序在第三个字符串中保持不变

要点:

可以用dp或dfs做,下面是dp的思路:

首先用定义一个数组dp[i][j],i代表了第一个字符串的第i个字母,j代表第二个字符串中第j个字母,那么可以通过dp[i][j]=1来表示串1的前i个字母和串2的前j个字母可以组成串3的前i+j个字母,如果等于0则说明不可以。

状态转移方程:dp[i][[j]=(c[i+j]==a[i]&&dp[i-1][j]||c[i+j]==b[j]&&dp[i][j-1])

要注意的是像第二个例子:cat  tree  catrtee,因为i和j最小都是从1开始的,c[i+j]不可能等于a[i],所以如果遇到这中一开始就c[i]=a[i]或b[i]的情况,对应的dp要先赋值为1,否则会对后面造成影响。

代码如下:

#include<stdio.h>
#include<string.h>int main()
{char a[300], b[300], c[600];int t,dp[300][300];int i, j, num = 1;;while (scanf("%d", &t) != EOF){while (t--){memset(dp, 0, sizeof(dp));scanf("%s %s %s", a + 1, b + 1, c + 1);//使字符串存储到数组中从1开始int len1 = strlen(a+1);int len2 = strlen(b+1);//计算长度时自然多算1个for (i = 1; i <= len1; i++)//这步是必要的,否则像第二个例子会出现错误{if (a[i] == c[i])dp[i][0] = 1;elsebreak;}for (i = 1; i <= len2; i++){if (b[i] == c[i])dp[0][i] = 1;elsebreak;}for (i = 1; i <= len1; i++)for (j = 1; j <= len2; j++){if (c[i + j] == a[i] && dp[i - 1][j])dp[i][j] = 1;if (c[i + j] == b[j] && dp[i][j - 1])dp[i][j] = 1;}printf("Data set %d: ", num++);if (dp[len1][len2])printf("yes\n");elseprintf("no\n");}}return 0;
}

还可以用dfs做:

如果直接用串3与串1,2比较一个个移动会出现如果有两个t不知道哪一个是串1的哪一个是串2的问题,如第二个input,dfs就很好的解决了这个问题,dfs是搜索了全部的情况,所以它考虑了两种情况,不管怎么样如果搜索成功说明是能够匹配的

还需要一点剪枝:串3的最后一个字母一定是串1或串2的最后一个字母

代码如下:

#include<stdio.h>
#include<string.h>
char a[300], b[300], c[600];
int len1, len2, len3;bool dfs(int x,int y,int z)
{if (x == len1&& y == len2&& z == len3)return true;if (a[x] == c[z]){if (dfs(x + 1, y, z + 1))return true;}if (b[y] == c[z]){if (dfs(x, y + 1, z + 1))return true;}return false;
}int main()
{int t,ans = 1;scanf("%d", &t);while (t--){bool flag = false;scanf("%s %s %s", a, b, c);len1 = strlen(a);len2 = strlen(b);len3 = strlen(c);if (c[len3 - 1] == a[len1 - 1] || c[len3 - 1] == b[len2 - 1])//剪枝flag = dfs(0, 0, 0);printf("Data set %d: ", ans++);if (flag)printf("yes\n");elseprintf("no\n");}return 0;
}