问几道版上的String面试题

原帖地址:mitbbs

第一:

input string s: microsoftfacebookgooglefacebookmicrosoft
p: xyzyx
output: if s matches pattern of p.
for example: x matches “microsoft”, y matches “facebook”, z matches “google”

这题好像是leetcode上的一个变异,但比原题难太多了,有人能提示个思路么?

第二:

“waeginsapnaabangpisebbasepgnccccapisdnfngaabndlrjngeuiogbbegbuoecccc”;
String s2 = “a+b+c-“;
s2的形式是一个字母加上一个符号,正号代表有两个前面的字符,负号代表有四个,也
就是说s2其实是”aabbcccc”,不考虑invalid。
在s1中,找出连续或者不连续的s2,也就是说从s1中找出”aa….bb…..cccc”,abc顺
序不能变,但是之间可以有零个或多个字符,返回共有多少个

这道也很眼熟,但正号和负号把这个题目变复杂了。。。。如果没有正负,用DP应该能做

第三:
给出一个没有cycle的图,找出中心,即到其他所有点的距离最近的点。
我想其实是给出一个tree,如果这tree是balanced,会不会root就是这个中点?
所以这个题目其实是balance一个tree。。。。。。

求大牛指点一二