Poj2092:字符串拉链

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

 

Reference:

 

此文中提供了该题目的非递归解法。

这里提供一个简明的递归代码。

codepad.org已验证。

Mar.7 2014 updated: 改为从左往右递归，减少了参数和判断。

#include<stdio.h>
#include<stdlib.h>

void isvalid(const char* input, const char*a, const char*b){
        if(input == NULL || a == NULL || b == NULL) return -1;
    if(!*input){
        if(!*a && !*b) return 1;
        return 0;
    }
    int ra,rb;
    ra = rb = 0;
    if(*input == *a )
        ra = isvalid(input+1,a+1,b);
    if(*input == *b)
        rb = isvalid(input+1,a,b+1);
    return ra|rb;

}



int main(){
    char* s1 = "cat";
    char* s2 = "tree";
    char* tar = "catrtee";
    int t = isvalid(tar,s1,s2);
    printf("%d\n",t);
}