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

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

4个回答

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

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);
}

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

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

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;
    }
}

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