Dado un texto y un patrón de comodines, implemente un algoritmo de coincidencia de patrones de comodines que encuentre si el patrón de comodines coincide con el texto. La coincidencia debe cubrir todo el texto (no texto parcial). El patrón comodín puede incluir los caracteres ‘?’ y ‘*’
- ‘?’ – coincide con cualquier carácter individual
- ‘*’: coincide con cualquier secuencia de caracteres (incluida la secuencia vacía)
Por ejemplo:
C++
// C++ program to implement wildcard
// pattern matching algorithm
#include <bits/stdc++.h>
using namespace std;
// Function that matches input str with
// given wildcard pattern
bool strmatch(char str[], char pattern[], int n, int m)
{
// empty pattern can only match with
// empty string
if (m == 0)
return (n == 0);
// lookup table for storing results of
// subproblems
bool lookup[n + 1][m + 1];
// initialize lookup table to false
memset(lookup, false, sizeof(lookup));
// empty pattern can match with empty string
lookup[0][0] = true;
// Only '*' can match with empty string
for (int j = 1; j <= m; j++)
if (pattern[j - 1] == '*')
lookup[0][j] = lookup[0][j - 1];
// fill the table in bottom-up fashion
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
// Two cases if we see a '*'
// a) We ignore ‘*’ character and move
// to next character in the pattern,
// i.e., ‘*’ indicates an empty sequence.
// b) '*' character matches with ith
// character in input
if (pattern[j - 1] == '*')
lookup[i][j]
= lookup[i][j - 1] || lookup[i - 1][j];
// Current characters are considered as
// matching in two cases
// (a) current character of pattern is '?'
// (b) characters actually match
else if (pattern[j - 1] == '?'
|| str[i - 1] == pattern[j - 1])
lookup[i][j] = lookup[i - 1][j - 1];
// If characters don't match
else
lookup[i][j] = false;
}
}
return lookup[n][m];
}
int main()
{
char str[] = "baaabab";
char pattern[] = "*****ba*****ab";
// char pattern[] = "ba*****ab";
// char pattern[] = "ba*ab";
// char pattern[] = "a*ab";
// char pattern[] = "a*****ab";
// char pattern[] = "*a*****ab";
// char pattern[] = "ba*ab****";
// char pattern[] = "****";
// char pattern[] = "*";
// char pattern[] = "aa?ab";
// char pattern[] = "b*b";
// char pattern[] = "a*a";
// char pattern[] = "baaabab";
// char pattern[] = "?baaabab";
// char pattern[] = "*baaaba*";
if (strmatch(str, pattern, strlen(str),
strlen(pattern)))
cout << "Yes" << endl;
else
cout << "No" << endl;
return 0;
}
Java
// Java program to implement wildcard
// pattern matching algorithm
import java.util.Arrays;
public class GFG {
// Function that matches input str with
// given wildcard pattern
static boolean strmatch(String str, String pattern,
int n, int m)
{
// empty pattern can only match with
// empty string
if (m == 0)
return (n == 0);
// lookup table for storing results of
// subproblems
boolean[][] lookup = new boolean[n + 1][m + 1];
// initialize lookup table to false
for (int i = 0; i < n + 1; i++)
Arrays.fill(lookup[i], false);
// empty pattern can match with empty string
lookup[0][0] = true;
// Only '*' can match with empty string
for (int j = 1; j <= m; j++)
if (pattern.charAt(j - 1) == '*')
lookup[0][j] = lookup[0][j - 1];
// fill the table in bottom-up fashion
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
// Two cases if we see a '*'
// a) We ignore '*'' character and move
// to next character in the pattern,
// i.e., '*' indicates an empty
// sequence.
// b) '*' character matches with ith
// character in input
if (pattern.charAt(j - 1) == '*')
lookup[i][j] = lookup[i][j - 1]
|| lookup[i - 1][j];
// Current characters are considered as
// matching in two cases
// (a) current character of pattern is '?'
// (b) characters actually match
else if (pattern.charAt(j - 1) == '?'
|| str.charAt(i - 1)
== pattern.charAt(j - 1))
lookup[i][j] = lookup[i - 1][j - 1];
// If characters don't match
else
lookup[i][j] = false;
}
}
return lookup[n][m];
}
// Driver code
public static void main(String args[])
{
String str = "baaabab";
String pattern = "*****ba*****ab";
// String pattern = "ba*****ab";
// String pattern = "ba*ab";
// String pattern = "a*ab";
// String pattern = "a*****ab";
// String pattern = "*a*****ab";
// String pattern = "ba*ab****";
// String pattern = "****";
// String pattern = "*";
// String pattern = "aa?ab";
// String pattern = "b*b";
// String pattern = "a*a";
// String pattern = "baaabab";
// String pattern = "?baaabab";
// String pattern = "*baaaba*";
if (strmatch(str, pattern, str.length(),
pattern.length()))
System.out.println("Yes");
else
System.out.println("No");
}
}
// This code is contributed by Sumit Ghosh
Python3
# Python program to implement wildcard
# pattern matching algorithm
# Function that matches input strr with
# given wildcard pattern
def strrmatch(strr, pattern, n, m):
# empty pattern can only match with
# empty string
if (m == 0):
return (n == 0)
# lookup table for storing results of
# subproblems
lookup = [[False for i in range(m + 1)] for j in range(n + 1)]
# empty pattern can match with empty string
lookup[0][0] = True
# Only '*' can match with empty string
for j in range(1, m + 1):
if (pattern[j - 1] == '*'):
lookup[0][j] = lookup[0][j - 1]
# fill the table in bottom-up fashion
for i in range(1, n + 1):
for j in range(1, m + 1):
# Two cases if we see a '*'
# a) We ignore ‘*’ character and move
# to next character in the pattern,
# i.e., ‘*’ indicates an empty sequence.
# b) '*' character matches with ith
# character in input
if (pattern[j - 1] == '*'):
lookup[i][j] = lookup[i][j - 1] or lookup[i - 1][j]
# Current characters are considered as
# matching in two cases
# (a) current character of pattern is '?'
# (b) characters actually match
else if (pattern[j - 1] == '?' or strr[i - 1] == pattern[j - 1]):
lookup[i][j] = lookup[i - 1][j - 1]
# If characters don't match
else:
lookup[i][j] = False
return lookup[n][m]
# Driver code
strr = "baaabab"
pattern = "*****ba*****ab"
# char pattern[] = "ba*****ab"
# char pattern[] = "ba*ab"
# char pattern[] = "a*ab"
# char pattern[] = "a*****ab"
# char pattern[] = "*a*****ab"
# char pattern[] = "ba*ab****"
# char pattern[] = "****"
# char pattern[] = "*"
# char pattern[] = "aa?ab"
# char pattern[] = "b*b"
# char pattern[] = "a*a"
# char pattern[] = "baaabab"
# char pattern[] = "?baaabab"
# char pattern[] = "*baaaba*"
if (strrmatch(strr, pattern, len(strr), len(pattern))):
print("Yes")
else:
print("No")
# This code is contributed by shubhamsingh10
C#
// C# program to implement wildcard
// pattern matching algorithm
using System;
class GFG {
// Function that matches input str with
// given wildcard pattern
static Boolean strmatch(String str,
String pattern,
int n, int m)
{
// empty pattern can only match with
// empty string
if (m == 0)
return (n == 0);
// lookup table for storing results of
// subproblems
Boolean[, ] lookup = new Boolean[n + 1, m + 1];
// initialize lookup table to false
for (int i = 0; i < n + 1; i++)
for (int j = 0; j < m + 1; j++)
lookup[i, j] = false;
// empty pattern can match with
// empty string
lookup[0, 0] = true;
// Only '*' can match with empty string
for (int j = 1; j <= m; j++)
if (pattern[j - 1] == '*')
lookup[0, j] = lookup[0, j - 1];
// fill the table in bottom-up fashion
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
// Two cases if we see a '*'
// a) We ignore '*'' character and move
// to next character in the pattern,
// i.e., '*' indicates an empty
// sequence.
// b) '*' character matches with ith
// character in input
if (pattern[j - 1] == '*')
lookup[i, j] = lookup[i, j - 1]
|| lookup[i - 1, j];
// Current characters are considered as
// matching in two cases
// (a) current character of pattern is '?'
// (b) characters actually match
else if (pattern[j - 1] == '?'
|| str[i - 1] == pattern[j - 1])
lookup[i, j] = lookup[i - 1, j - 1];
// If characters don't match
else
lookup[i, j] = false;
}
}
return lookup[n, m];
}
// Driver Code
public static void Main(String[] args)
{
String str = "baaabab";
String pattern = "*****ba*****ab";
// String pattern = "ba*****ab";
// String pattern = "ba*ab";
// String pattern = "a*ab";
// String pattern = "a*****ab";
// String pattern = "*a*****ab";
// String pattern = "ba*ab****";
// String pattern = "****";
// String pattern = "*";
// String pattern = "aa?ab";
// String pattern = "b*b";
// String pattern = "a*a";
// String pattern = "baaabab";
// String pattern = "?baaabab";
// String pattern = "*baaaba*";
if (strmatch(str, pattern, str.Length,
pattern.Length))
Console.WriteLine("Yes");
else
Console.WriteLine("No");
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// JavaScript program to implement wildcard
// pattern matching algorithm
// Function that matches input str with
// given wildcard pattern
function strmatch(str, pattern, n, m)
{
// empty pattern can only match with
// empty string
if (m == 0)
return (n == 0);
// lookup table for storing results of
// subproblems
// initialize lookup table to false
let lookup = new Array(n + 1).fill(false).map(()=>new Array(m + 1).fill(false));
// empty pattern can match with empty string
lookup[0][0] = true;
// Only '*' can match with empty string
for (let j = 1; j <= m; j++)
if (pattern[j - 1] == '*')
lookup[0][j] = lookup[0][j - 1];
// fill the table in bottom-up fashion
for (let i = 1; i <= n; i++) {
for (let j = 1; j <= m; j++) {
// Two cases if we see a '*'
// a) We ignore ‘*’ character and move
// to next character in the pattern,
// i.e., ‘*’ indicates an empty sequence.
// b) '*' character matches with ith
// character in input
if (pattern[j - 1] == '*')
lookup[i][j]
= lookup[i][j - 1] || lookup[i - 1][j];
// Current characters are considered as
// matching in two cases
// (a) current character of pattern is '?'
// (b) characters actually match
else if (pattern[j - 1] == '?'
|| str[i - 1] == pattern[j - 1])
lookup[i][j] = lookup[i - 1][j - 1];
// If characters don't match
else
lookup[i][j] = false;
}
}
return lookup[n][m];
}
// driver code
let str = "baaabab";
let pattern = "*****ba*****ab";
// let pattern = "ba*****ab";
// let pattern = "ba*ab";
// let pattern = "a*ab";
// let pattern = "a*****ab";
// let pattern = "*a*****ab";
// let pattern = "ba*ab****";
// let pattern = "****";
// let pattern = "*";
// let pattern = "aa?ab";
// let pattern = "b*b";
// let pattern = "a*a";
// let pattern = "baaabab";
// let pattern = "?baaabab";
// let pattern = "*baaaba*";
if (strmatch(str, pattern, str.length,pattern.length))
document.write("Yes","</br>")
else
document.write("No","</br>")
// This code is contributed by shinjanpatra
</script>
C++
// C++ program to implement wildcard
// pattern matching algorithm
#include <bits/stdc++.h>
using namespace std;
// Function that matches input str with
// given wildcard pattern
vector<vector<int> > dp;
int finding(string& s, string& p, int n, int m)
{
// return 1 if n and m are negative
if (n < 0 && m < 0)
return 1;
// return 0 if m is negative
if (m < 0)
return 0;
// return n if n is negative
if (n < 0)
{
// while m is positive
while (m >= 0)
{
if (p[m] != '*')
return 0;
m--;
}
return 1;
}
// if dp state is not visited
if (dp[n][m] == -1)
{
if (p[m] == '*')
{
return dp[n][m] = finding(s, p, n - 1, m)
|| finding(s, p, n, m - 1);
}
else
{
if (p[m] != s[n] && p[m] != '?')
return dp[n][m] = 0;
else
return dp[n][m]
= finding(s, p, n - 1, m - 1);
}
}
// return dp[n][m] if dp state is previsited
return dp[n][m];
}
bool isMatch(string s, string p)
{
dp.clear();
// resize the dp array
dp.resize(s.size() + 1, vector<int>(p.size() + 1, -1));
return dp[s.size()][p.size()]
= finding(s, p, s.size() - 1, p.size() - 1);
}
// Driver code
int main()
{
string str = "baaabab";
string pattern = "*****ba*****ab";
// char pattern[] = "ba*****ab";
// char pattern[] = "ba*ab";
// char pattern[] = "a*ab";
// char pattern[] = "a*****ab";
// char pattern[] = "*a*****ab";
// char pattern[] = "ba*ab****";
// char pattern[] = "****";
// char pattern[] = "*";
// char pattern[] = "aa?ab";
// char pattern[] = "b*b";
// char pattern[] = "a*a";
// char pattern[] = "baaabab";
// char pattern[] = "?baaabab";
// char pattern[] = "*baaaba*";
if (isMatch(str, pattern))
cout << "Yes" << endl;
else
cout << "No" << endl;
return 0;
}
Javascript
<script>
// JavaScript program to implement wildcard
// pattern matching algorithm
// Function that matches input str with
// given wildcard pattern
let dp = [];
function finding(s, p, n, m)
{
// return 1 if n and m are negative
if (n < 0 && m < 0)
return 1;
// return 0 if m is negative
if (m < 0)
return 0;
// return n if n is negative
if (n < 0)
{
// while m is positive
while (m >= 0)
{
if (p[m] != '*')
return 0;
m--;
}
return 1;
}
// if dp state is not visited
if (dp[n][m] == -1)
{
if (p[m] == '*')
{
return dp[n][m] = finding(s, p, n - 1, m)
|| finding(s, p, n, m - 1);
}
else
{
if (p[m] != s[n] && p[m] != '?')
return dp[n][m] = 0;
else
return dp[n][m]
= finding(s, p, n - 1, m - 1);
}
}
// return dp[n][m] if dp state is previsited
return dp[n][m];
}
function isMatch(s, p)
{
dp = [];
// resize the dp array
dp = new Array(s.length+1).fill(1).map(()=>new Array(p.length+1).fill(-1));
return dp[s.length][p.length]
= finding(s, p, s.length - 1, p.length - 1);
}
// Driver code
let str = "baaabab";
let pattern = "*****ba*****ab";
// char pattern[] = "ba*****ab";
// char pattern[] = "ba*ab";
// char pattern[] = "a*ab";
// char pattern[] = "a*****ab";
// char pattern[] = "*a*****ab";
// char pattern[] = "ba*ab****";
// char pattern[] = "****";
// char pattern[] = "*";
// char pattern[] = "aa?ab";
// char pattern[] = "b*b";
// char pattern[] = "a*a";
// char pattern[] = "baaabab";
// char pattern[] = "?baaabab";
// char pattern[] = "*baaaba*";
if (isMatch(str, pattern))
console.log("Yes")
else
console.log("No")
// This code is contributed by shinjanpatra
</script>
C++
// C++ program to implement wildcard
// pattern matching algorithm
#include <bits/stdc++.h>
using namespace std;
// Function that matches input str with
// given wildcard pattern
bool strmatch(char str[], char pattern[], int m, int n)
{
// lookup table for storing results of
// subproblems
vector<bool> prev(m + 1, false), curr(m + 1, false);
// empty pattern can match with empty string
prev[0] = true;
// fill the table in bottom-up fashion
for (int i = 1; i <= n; i++) {
bool flag = true;
for (int ii = 1; ii < i; ii++) {
if (pattern[ii - 1] != '*') {
flag = false;
break;
}
}
curr[0] = flag; // for every row we are assigning
// 0th column value.
for (int j = 1; j <= m; j++) {
// Two cases if we see a '*'
// a) We ignore ‘*’ character and move
// to next character in the pattern,
// i.e., ‘*’ indicates an empty sequence.
// b) '*' character matches with ith
// character in input
if (pattern[i - 1] == '*')
curr[j] = curr[j - 1] || prev[j];
// Current characters are considered as
// matching in two cases
// (a) current character of pattern is '?'
// (b) characters actually match
else if (pattern[i - 1] == '?'
|| str[j - 1] == pattern[i - 1])
curr[j] = prev[j - 1];
// If characters don't match
else
curr[j] = false;
}
prev = curr;
}
return prev[m];
}
int main()
{
char str[] = "baaabab";
char pattern[] = "*****ba*****ab";
// char pattern[] = "ba*****ab";
// char pattern[] = "ba*ab";
// char pattern[] = "a*ab";
// char pattern[] = "a*****ab";
// char pattern[] = "*a*****ab";
// char pattern[] = "ba*ab****";
// char pattern[] = "****";
// char pattern[] = "*";
// char pattern[] = "aa?ab";
// char pattern[] = "b*b";
// char pattern[] = "a*a";
// char pattern[] = "baaabab";
// char pattern[] = "?baaabab";
// char pattern[] = "*baaaba*";
if (strmatch(str, pattern, strlen(str),
strlen(pattern)))
cout << "Yes" << endl;
else
cout << "No" << endl;
return 0;
}
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA