LeetCode-符串通配符

自己处理输入输出

• 描述：

  实现如下2个通配符：

  1. *：匹配0个或以上的字符（字符由英文字母和数字0-9组成，不区分大小写。下同）

  2. ？：匹配1个字符

     input:先输入一个带有通配符的字符串，再输入一个需要匹配的字符串。如：

     te?t*.*
txt12.xls

     output:返回匹配的结果，正确输出true，错误输出false。如上例返回false。

• 思路：

  1. 终止条件先后有序
  2. 对于if(*str1 == '*')中，三个递归match，好好体会三种情况
     1. a*c, ac。*与0个匹配
     2. a*c, abc。*与1个匹配
     3. a*c, abbbc。*与多个匹配

• 实现：

  #include<iostream>
  using namespace std;
  
  bool match(char* str1, char* str2){
      // 终止条件 同时到字符串尾，放回true
      if(*str1 == '\0'  && *str2 == '\0')
          return true;
      // 只有一个到尾，返回false。不会两者都到尾，因为上一个if判断过了
      else if(*str1 == '\0' || *str2 == '\0')
          return false;
      // 对于‘？’，一定匹配，所以查看下一对字符
      if(*str1 == '?')
          return match(str1+1, str2+1);
      // 当两个字符相等，一定匹配，查看下一对字符
      else if(*str1 == *str2)
          return match(str1+1, str2+1);
          
      // 对于‘*’, 匹配零个，一个或多个
      else if(*str1 == '*')
          return match(str1+1, str2) ||    //零个
                 match(str1+1, str2+1) ||  // 一个
                 match(str1, str2+1);      // 多个
      return false;
  }
  
  int main(){
      char str1[100], str2[100];
      while(cin>>str1>>str2){
          if(match(str1, str2))
              cout<<"true"<<endl;
          else
              cout<<"false"<<endl;
      }
      return 0;
  }