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

## 本文概述

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

## 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”不匹配。

• 回顶