Chinaunix首页 | 论坛 | 博客
  • 博客访问: 1006614
  • 博文数量: 150
  • 博客积分: 3017
  • 博客等级: 少校
  • 技术积分: 3829
  • 用 户 组: 普通用户
  • 注册时间: 2011-11-19 14:40
个人简介

Now in Baidu WISE team

文章分类

全部博文(150)

文章存档

2014年(8)

2013年(31)

2012年(111)

分类: C/C++

2013-01-08 13:51:42

给定三个字符串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: 改为从左往右递归,减少了参数和判断。


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

  3. void isvalid(const char* input, const char*a, const char*b){
  4.         if(input == NULL || a == NULL || b == NULL) return -1;
  5.     if(!*input){
  6.         if(!*a && !*b) return 1;
  7.         return 0;
  8.     }
  9.     int ra,rb;
  10.     ra = rb = 0;
  11.     if(*input == *a )
  12.         ra = isvalid(input+1,a+1,b);
  13.     if(*input == *b)
  14.         rb = isvalid(input+1,a,b+1);
  15.     return ra|rb;
  16.         
  17. }



  18. int main(){
  19.     char* s1 = "cat";
  20.     char* s2 = "tree";
  21.     char* tar = "catrtee";
  22.     int t = isvalid(tar,s1,s2);
  23.     printf("%d\n",t);
  24. }


阅读(1259) | 评论(0) | 转发(1) |
给主人留下些什么吧!~~