算法题（字符串匹配，其中一个字符串包含通配符） _字符串匹配介绍

本文概述

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 ] = = '*' andlen (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# 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小组审查。如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请写评论。