一个有关如何合并字符串的问题,算法请教怎么实现的思路?

Problem Description
Given three strings a, b and c, your mission is to check whether c is the combine string of a and b.
A string c is said to be the combine string of a and b if and only if c can be broken into two subsequences, when you read them as a string, one equals to a, and the other equals to b.
For example, adebcf'' is a combine string ofabc'' and ``def''.

Input
Input file contains several test cases (no more than 20). Process to the end of file.
Each test case contains three strings a, b and c (the length of each string is between 1 and 2000).

Output
For each test case, print Yes'', if c is a combine string of a and b, otherwise printNo''.

Sample Input
abc
def
adebcf
abc
def
abecdf

Sample Output
Yes
No

0

3个回答

写一个递归的吧,用栈可以转化成非递归,你自己转化吧。可以通过字符种类和数量简单的做一下预判。下面是伪代码:

int res=0;
a='ab'
b='ac'
c='acab'
void f(int ai,int bi,int ci){
    if(ai+bi+ci== a.len+b.len+c.len-1){ res=1; return;}
    if(ai==a.len or bi==b.len or ci==c.len) return;
    if(a[ai]==c[ci]) f(ai+1,bi,ci+1);
    if(a[bi]==c[ci]) f(ai,bi+1,ci+1);
}
int main(){
    f(0,0,0);
    print(res);
}
-1

统计a,b,c字符串中字符出现的个数得到amap,bmap,cmap,然后合并amap,bmap,然后和cmap的元素逐个比较

-2
weixin_29444181
哈喽大海豚 回复Moluth: 好吧,我没看到后面的sample里面要求有序。。。
6 个月之前 回复
Moluth
Moluth 大兄弟,你这回答,真是胡闹,该问题不是这么简单的
6 个月之前 回复

adebcf 遍历
a,从另外两个头部出a,有继续,没有就是NO
直到遍历完毕,此时另外两个也刚好全部匹配
以下是java实现,英文不好,不知道我有没有理解错题意。

改成了递归,之前没考虑另外一种情况


public class Test {
    public static void main(String args[]) {
        System.out.println(combine("ab", "ac", "acab"));
    }

    public static boolean combine(String a, String b, String c) {
        if (a.length() == 0) {
            return b.equals(c);
        } else if (b.length() == 0) {
            return a.equals(c);
        }
        char cha = a.charAt(0), chb = b.charAt(0), chc = c.charAt(0);
        if (cha == chc && chb == chc) {
            return combine(a.substring(1), b, c.substring(1)) 
                    || combine(a, b.substring(1), c.substring(1));
        } else if (cha == chc) {
            return combine(a.substring(1), b, c.substring(1));
        } else if (chb == chc) {
            return combine(a, b.substring(1), c.substring(1));
        }
        return false;
    }
}

-2
miaoch
miaoch 回复Moluth: 改了一下 应该没问题了,非空判断什么的就先不写了
6 个月之前 回复
miaoch
miaoch 回复Moluth: 恩 是的,没注意
6 个月之前 回复
Moluth
Moluth 兄弟呀,你这个明显不行的,例如:a='ac' b='ab' c='abac' 安照你的代码,很明显会返回false的,实际结果是true
6 个月之前 回复
Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!

相似问题

3
一个有关如何合并字符串的问题,算法请教怎么实现的思路?
0
求问一个比较典型的算法问题,要求计算每个商品的价格,怎么写?
0
这个问题,长度一大,计算就很慢,有什么办法可以优化程序算法?
1
这是一个有关魔方的问题,请问怎么计算旋转的步数
0
请问大家这个问题用C语言怎么才能实现运行呢?总是超时间
0
一个求最大公约数的题目,要求输出的是多个数字的最大公约数。
1
一个有关于:逻辑推理方面的算法,用C语言解决,谢谢了
2
输出结果精确6位小数,这个用C语言怎么实现呢?
0
组合数的排列算法问题,请问这里的序列怎么得到,用C语言。。。
1
求问这个问题里输出inf用C语言是怎么实现的?不是很清楚,求解释。
1
带错误检查的表达式计算器用C语言怎么实现的呢?
1
这个问题的C语言的算法是怎么实现的?没有一点思路
1
用C语言实现多边形顶点计算的一个问题,具体看下面
1
遇到一个比较模糊的问题,这个问题用二判定怎么实现呢?
2
这个算法问题,请大身看下怎么解决,如何输出公因数
1
这个算法问题如果要用递归来做,应该怎么做呢?
2
判断一个序列是不是等比级数。用C语言解答这个问题怎么做呢?
2
请问这个问题用C语言怎么代码才能实现???求思路解答
2
最小生成树方面的一个问题,用C语言怎么解决的????
1
一个有关方程等式的问题,用C语言求大神快点来帮助