首页 > 笔试面试题, 算法 数据结构 > 百度面试题:POJ 2192 - Zipper

百度面试题:POJ 2192 - Zipper

2012年9月30日 发表评论 阅读评论
文章作者:Yx.Ac   文章来源:勇幸|Thinking (http://www.ahathinking.com)   转载请注明,谢谢合作。

---

百度二面的时候有一道题目没有答上来,回来一查,原来是POJ上的原题,是一个DP问题,当时有向这方面想,但始终没有找出重叠子问题,网上看到别人定义的子问题,感觉真心简单,关键看是否能找出子问题了,这个积累不是一时半日的,自己还是太菜。刚刚到POJ上AC了这道题,附题目链接:

POJ 2192: http://poj.org/problem?id=2192

题意:就是给定三个字符串A,B,C;判断C能否由AB中的字符组成,同时这个组合后的字符顺序必须是A,B中原来的顺序,不能逆序;例如:A:mnl,B:xyz;如果C为mnxylz,就符合题意;如果C为mxnzly,就不符合题意,原因是z与y顺序不是B中顺序。

DP求解:定义dp[i][j]表示A中前i个字符与B中前j个字符是否能组成C中的前 (i+j) 个字符,如果能标记true,如果不能标记false;

有了这个定义,我们就可以找出状态转移方程了,初始状态dp[0][0] = 1:

dp[i][j] = 1 如果 dp[i-1][j] == 1 && C[i+j-1] == A[i-1]
dp[i][j] = 1 如果 dp[i][j-1] == 1 && C[i+j-1] == B[j-1]

代码如下:

#include<iostream>
using namespace std;

char A[201];
char B[201];
char C[401];

int N; /* 测试次数 */

/* dp[i][j] 表示A前i个字符与B前j个字符
   是否能构成C前i+j个字符
*/
short int dp[201][201];

int main()
{
	scanf("%d", &N);
	for(int k = 1; k <= N; ++k)   /* N个测试用例 */
	{
		memset(dp,0,sizeof dp);
		scanf("%s %s %s", A, B, C);
		int lenA = strlen(A);
		int lenB = strlen(B);

		dp[0][0] = 1;

		for(int i = 0; i <= lenA; ++i)
		{
			for(int j = 0; j <= lenB; ++j)
			{
				if(i > 0 && (dp[i-1][j] == 1) && (C[i+j-1] == A[i-1]))
				{
					dp[i][j] = 1;
				}
				if(j > 0 && (dp[i][j-1] == 1) && (C[i+j-1] == B[j-1]))
				{
					dp[i][j] = 1;
				}
			}
		}

		printf("Data set %d: %s\n", k, dp[lenA][lenB] ? "yes" : "no");
	}
	return 0;
}

参考资料中有用DFS实现这个题目的,DFS真心强大啊@HFC,sigh,修炼啊修炼。

DFS代码如下:

#include<iostream>
using namespace std;

char A[201];
char B[201];
char C[401];

int N; /* 测试次数 */

int DFS(int x, int y)
{
	if(x == -1 && y == -1)
		return 1;
	if(x >= 0 && A[x] == C[x+y+1])
	{
		if(DFS(x-1,y))
			return 1;
	}
	if(y >= 0 && B[y] == C[x+y+1])
	{
		if(DFS(x,y-1))
			return 1;
	}
	return 0;
}

int main()
{
	scanf("%d", &N);
	for(int k = 1; k <= N; ++k)   /* N个测试用例 */
	{
		scanf("%s %s %s", A, B, C);
		printf("Data set %d: %s\n", k, DFS(strlen(A)-1,strlen(B)-1) ? "yes" : "no");
	}
	return 0;
}

以上代码均在POJ验证过,本文相关代码可以到这里下载。

(全文完)

参考资料:http://blog.csdn.net/morgan_xww/article/details/5596030

  • 那闯

    第二种算法我觉得是投机取巧的算法,时间至少为O(2^n),
    只是poj测试数据不足才过的。

  • liang

    dp[i][j] = 1 如果 dp[i-1][j] == 1 && C[i+j-1] == A[i-1]
    dp[i][j] = 1 如果 dp[i][j-1] == 1 && C[i+j-1] == B[j-1]
    这两种情况,&&后面的条件怎么解释的?
    请指教,谢谢。

    • Yx.Ac

      @liang C[i+j-1] == A[i-1]表示C那个位置的字符来自于A,同理下面的表示那个字符来自B

  • sc

    直接从C字符串的初始位置开始比较A的初始位置,看字符是否相同,相同则C和A均后移;不同则比较B的,相同将C和B均后移,不同说明false,即A和B不能组成C。这样不更简单?

    • Yx.Ac

      @sc 这样的方法是不可行的;如果C和A的相同也和B的相同呢?该移动谁?实际上如果这样,是需要分两种情况判断的,从上面的DP方法和DFS方法都可以看出,只要有一种移动情况将来可以组成就是对的;举个例子,A=cat,B=tree,C=catrtee,当移动到C的第一个“t”时,此时A如果程序移动A的指针就是错的,移动B的就是对的,所以这种思路不可行;必须将A和B的指针都移动的情况全考虑,如果这种情况比较多,则程序实现起来简单地靠指针移动个人感觉是无法实现的;欢迎继续交流,谢谢,/握手

      • http://xanarry.me xanarry

        那样是可行的, 如果在t处有a和b两个来源, 可以在t的位置标记为2, 正常标记为1,说明有一个来源, 如果在后面再次遇到t时, 找到前面来源为2的t, 将其置为1, 因为另外一个被拿到了后面新遇到的t, 这样就能解决了, 最后我们遍历c字符串, 如果每个字符对于的来源都为1,那么输出yes, 否则no

  • Yx.Ac

    您可能对题意有误会,C中的mm是重复,这个是不可以的,即C相对于AB的组合多出了一个m;另DFS在POJ上submit过了,嘿@normal

  • normal

    我怎么觉得DFS有问题啊,如果A:mnl,B:xyz;如果C为mmnxylz,DFS的结果就是0了啊,但是A,B可以组成C啊