阿玛松 vo 挂经

请问第三题是考虑三种情况吗？

Z是AB的顺序组合，Z是AB的乱序组合，Z不是AB的组合，只有第二种情况返回true

先用map判断Z是不是由AB组成的，如果是再用DP或dfs去判断Z是不是顺序组合，不是就返回true?

补充内容 (2019-2-21 08:17):
第二题

private boolean helper(String X,String Y,String Z,int indx,int indy,int indz){
    if (indx >= X.length() || indy >= Y.length() )return false;
    if (X.charAt(indx) == Z.charAt(indz) && Y.charAt(indy) == Z.charAt(indz))
          return helper(X,Y,Z,indx + 1,indy,indz + 1) || helper(X,Y,Z,indx,indy + 1,indz + 1);
    if (X.charAt(indx) == Z.charAt(indz))return helper(X,Y,Z,indx + 1,indy,indz + 1);
    if(Y.charAt(indy) == Z.charAt(indz)) return helper(X,Y,Z,indx,indy + 1,indz + 1);
    return false;
}

boolean helper(String X,String Y,String Z,int indx,int indy,int indz){

}

boolean helper(String X,String Y,String Z,int indx,int indy,int indz){

}

....本来想再写个dp的，电脑抽风连发两个....溜了

bigworld 发表于 2019/02/21 07:34:53
楼主请问是蠡口 酒气 吗？就是去判断是否是顺序组合

是的！可惜没做过tt

zjswhhh 发表于 2019/02/21 07:54:31
第二题是dp吗？

最好应该是dp的 但是面试官似乎希望写个暴力一点的

ff12 发表于 2019/02/21 08:16:53
请问第三题是考虑三种情况吗？

Z是AB的顺序组合，Z是AB的乱序组合，Z不是AB的组合，只有第二种情况返回true

先用map判断Z是不是由AB组成的，如果是再用DP或dfs去判断Z是不是...

看看leetcode 97应该就是这道题

dfs, 三个point i,j,k 分别指向首字母， 判断 i==k || j == k 都不满足就return false， recursion 所有的情况，直到 i+j == z.length()

yuxudong199 发表于 2019-2-22 02:26
dfs, 三个point i,j,k 分别指向首字母， 判断 i==k || j == k 都不满足就return false， recursion 所有的 ...

是这样的