算法题：字符串匹配，其中一个字符串包含通配符

本文概述

• C ++
• Java
• python
• C#

给定两个字符串, 其中第一个字符串可以包含通配符, 第二个字符串是普通字符串。编写一个函数, 如果两个字符串匹配, 则返回true。以下是第一个字符串中允许使用的通配符。

* --> Matches with 0 or more instances of any character or set of characters.
? --> Matches with any one character.

例如, ” g * ks”匹配与” geeks”匹配。字符串” ge？ks *”与” srcmini”匹配(在第一个字符串的末尾注明” *”)。但是” g * k”与” gee”不匹配, 因为第二个字符串中没有字符” k”。

C ++

// A C program to match wild card characters
#include <stdio.h>
#include <stdbool.h>
  
// The main function that checks if two given strings
// match. The first string may contain wildcard characters
bool match( char *first, char * second)
{
     // If we reach at the end of both strings, we are done
     if (*first == '\0' && *second == '\0' )
         return true ;
  
     // Make sure that the characters after '*' are present
     // in second string. This function assumes that the first
     // string will not contain two consecutive '*'
     if (*first == '*' && *(first+1) != '\0' && *second == '\0' )
         return false ;
  
     // If the first string contains '?', or current characters
     // of both strings match
     if (*first == '?' || *first == *second)
         return match(first+1, second+1);
  
     // If there is *, then there are two possibilities
     // a) We consider current character of second string
     // b) We ignore current character of second string.
     if (*first == '*' )
         return match(first+1, second) || match(first, second+1);
     return false ;
}
  
// A function to run test cases
void test( char *first, char *second)
{  match(first, second)? puts ( "Yes" ): puts ( "No" ); }
  
// Driver program to test above functions
int main()
{
     test( "g*ks" , "geeks" ); // Yes
     test( "ge?ks*" , "srcmini" ); // Yes
     test( "g*k" , "gee" );  // No because 'k' is not in second
     test( "*pqrs" , "pqrst" ); // No because 't' is not in first
     test( "abc*bcd" , "abcdhghgbcd" ); // Yes
     test( "abc*c?d" , "abcd" ); // No because second must have 2
                              // instances of 'c'
     test( "*c*d" , "abcd" ); // Yes
     test( "*?c*d" , "abcd" ); // Yes
     return 0;
}

Java

// Java program to match wild card characters 
class GFG 
{
  
// The main function that checks if 
// two given strings match. The first string 
// may contain wildcard characters
static boolean match(String first, String second) 
{
  
     // If we reach at the end of both strings, // we are done
     if (first.length() == 0 && second.length() == 0 )
         return true ;
  
     // Make sure that the characters after '*' 
     // are present in second string. 
     // This function assumes that the first
     // string will not contain two consecutive '*'
     if (first.length() > 1 && first.charAt( 0 ) == '*' && 
                               second.length() == 0 )
         return false ;
  
     // If the first string contains '?', // or current characters of both strings match
     if ((first.length() > 1 && first.charAt( 0 ) == '?' ) || 
         (first.length() != 0 && second.length() != 0 && 
          first.charAt( 0 ) == second.charAt( 0 )))
         return match(first.substring( 1 ), second.substring( 1 ));
  
     // If there is *, then there are two possibilities
     // a) We consider current character of second string
     // b) We ignore current character of second string.
     if (first.length() > 0 && first.charAt( 0 ) == '*' )
         return match(first.substring( 1 ), second) || 
                match(first, second.substring( 1 ));
     return false ;
}
  
// A function to run test cases
static void test(String first, String second)
{
     if (match(first, second))
         System.out.println( "Yes" );
     else
         System.out.println( "No" );
}
  
// Driver Code
public static void main(String[] args) 
{
     test( "g*ks" , "geeks" ); // Yes
     test( "ge?ks*" , "srcmini" ); // Yes
     test( "g*k" , "gee" ); // No because 'k' is not in second
     test( "*pqrs" , "pqrst" ); // No because 't' is not in first
     test( "abc*bcd" , "abcdhghgbcd" ); // Yes
     test( "abc*c?d" , "abcd" ); // No because second must have 2
                             // instances of 'c'
     test( "*c*d" , "abcd" ); // Yes
     test( "*?c*d" , "abcd" ); // Yes
}
}
  
// This code is contributed by
// sanjeev2552

python

# Python program to match wild card characters
  
# The main function that checks if two given strings match.
# The first string may contain wildcard characters
def match(first, second):
  
     # If we reach at the end of both strings, we are done
     if len (first) = = 0 and len (second) = = 0 :
         return True
  
     # Make sure that the characters after '*' are present
     # in second string. This function assumes that the first
     # string will not contain two consecutive '*'
     if len (first) > 1 and first[ 0 ] = = '*' and  len (second) = = 0 :
         return False
  
     # If the first string contains '?', or current characters
     # of both strings match
     if ( len (first) > 1 and first[ 0 ] = = '?' ) or ( len (first) ! = 0
         and len (second) ! = 0 and first[ 0 ] = = second[ 0 ]):
         return match(first[ 1 :], second[ 1 :]);
  
     # If there is *, then there are two possibilities
     # a) We consider current character of second string
     # b) We ignore current character of second string.
     if len (first) ! = 0 and first[ 0 ] = = '*' :
         return match(first[ 1 :], second) or match(first, second[ 1 :])
  
     return False
  
# A function to run test cases
def test(first, second):
     if match(first, second):
         print "Yes"
     else :
         print "No"
  
# Driver program
test( "g*ks" , "geeks" ) # Yes
test( "ge?ks*" , "srcmini" ) # Yes
test( "g*k" , "gee" ) # No because 'k' is not in second
test( "*pqrs" , "pqrst" ) # No because 't' is not in first
test( "abc*bcd" , "abcdhghgbcd" ) # Yes
test( "abc*c?d" , "abcd" ) # No because second must have 2 instances of 'c'
test( "*c*d" , "abcd" ) # Yes
test( "*?c*d" , "abcd" ) # Yes
  
# This code is contributed by BHAVYA JAIN and ROHIT SIKKA

C#

// C# program to match wild card characters 
using System;
  
class GFG 
{
   
// The main function that checks if 
// two given strings match. The first string 
// may contain wildcard characters
static bool match(String first, String second) 
{
   
     // If we reach at the end of both strings, // we are done
     if (first.Length == 0 && second.Length == 0)
         return true ;
   
     // Make sure that the characters after '*' 
     // are present in second string. 
     // This function assumes that the first
     // string will not contain two consecutive '*'
     if (first.Length > 1 && first[0] == '*' && 
                               second.Length == 0)
         return false ;
   
     // If the first string contains '?', // or current characters of both strings match
     if ((first.Length > 1 && first[0] == '?' ) || 
         (first.Length != 0 && second.Length != 0 && 
          first[0] == second[0]))
         return match(first.Substring(1), second.Substring(1));
   
     // If there is *, then there are two possibilities
     // a) We consider current character of second string
     // b) We ignore current character of second string.
     if (first.Length > 0 && first[0] == '*' )
         return match(first.Substring(1), second) || 
                match(first, second.Substring(1));
     return false ;
}
   
// A function to run test cases
static void test(String first, String second)
{
     if (match(first, second))
         Console.WriteLine( "Yes" );
     else
         Console.WriteLine( "No" );
}
   
// Driver Code
public static void Main(String[] args) 
{
     test( "g*ks" , "geeks" ); // Yes
     test( "ge?ks*" , "srcmini" ); // Yes
     test( "g*k" , "gee" ); // No because 'k' is not in second
     test( "*pqrs" , "pqrst" ); // No because 't' is not in first
     test( "abc*bcd" , "abcdhghgbcd" ); // Yes
     test( "abc*c?d" , "abcd" ); // No because second must have 2
                             // instances of 'c'
     test( "*c*d" , "abcd" ); // Yes
     test( "*?c*d" , "abcd" ); // Yes
}
}
  
// This code is contributed by Rajput-Ji

输出如下：

Yes
Yes
No
No
Yes
No
Yes
Yes

行使

1)

在上述解决方案中, 第一个字符串的所有非通配字符必须存在第二个字符串, 并且第二个字符串的所有字符必须与第一个字符串的普通字符或通配符匹配。扩展上述解决方案使其与其他解决方案一样工作

模式搜索解决方案

其中第一个字符串是模式, 第二个字符串是文本, 我们应该在第二个中打印所有出现的第一个字符串。

2)编写一个模式搜索函数, 其中”？”的含义相同, 但是” *”表示在” *”之前出现0个或多个字符。例如, 如果第一个字符串是” a * b”, 则它与” aaab”匹配, 但与” abb”不匹配。

本文作者：维沙尔乔杜里并由srcmini小组审查。如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请写评论。