Dadas dos strings de texto y patrón de longitud M y N respectivamente, la tarea es verificar si el patrón coincide con el texto o no. Si se encuentra que es cierto, escriba «Sí» . De lo contrario, escriba “No” .
Nota: el patrón puede incluir los caracteres ‘*’ y ‘•’
- ‘*’ coincide con cero o más apariciones del carácter justo antes del carácter actual
- ‘•’ coincide con cualquier carácter de señal.
Ejemplos:
Entrada: patrón = “ge*ksforgeeks”, texto = “geeksforgeeks”
Salida: Sí
Explicación:
Reemplazar * con ‘e’, modifica el patrón igual a “geeksforgeeks”.
Por lo tanto, la salida requerida es Sí.Entrada: patrón = “ab*d”, texto = “abcds”
Salida: No
Explicación: El patrón dado no puede coincidir con el texto.
Enfoque ingenuo: el enfoque más simple para resolver este problema es iterar sobre los caracteres de ambas strings usando recursion . Si el carácter actual es ‘.’ , reemplace el carácter actual por cualquier carácter y recurra para el patrón restante y la string de texto . De lo contrario, si el carácter actual es ‘*’ , recurra al texto restante y verifique si coincide con el resto del patrón o no. Si se encuentra que es cierto, escriba «Sí» . De lo contrario, escriba “No” .
Complejidad temporal: O((M + N) * 2 (M + N / 2) )
Espacio auxiliar: O((M + N) * 2 (M + N / 2) )
Enfoque eficiente: el enfoque anterior se puede optimizar mediante la programación dinámica . Las siguientes son las relaciones de recurrencia:
- Inicialice una array 2D , dp[M + 1][N + 1] , donde dp[i][j] compruebe si la substring { text[0], …, text[i] } coincide con la substring { pattern[ 0], … patrón[j] } o no.
- Itere sobre los caracteres de ambas strings y complete la array dp[][] según la siguiente relación de recurrencia:
- Si text[i] y pattern[j] son iguales, complete dp[i + 1][j + 1] = dp[i][j] .
- Si patrón[j] es ‘.’ luego complete dp[i + 1][j + 1] = dp[i][j].
- Si patrón[j] es ‘*’ , compruebe las siguientes condiciones:
- Si texto[i] no es igual a patrón[j – 1] y patrón[j – 1] no es igual a ‘.’ , luego complete dp[i + 1][j + 1] = dp[i + 1][j – 1] .
- De lo contrario, complete dp[i + 1][j + 1] = (dp[i + 1][j] || dp[i][j + 1] || dp[i + 1][j – 1]) .
- Finalmente, imprima el valor de dp[M][N] .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to check if the pattern
// consisting of '*', '.' and lowercase
// characters matches the text or not
int isMatch(string text, string pattern)
{
// Base Case
if (text == "" or pattern == "")
return false;
// Stores length of text
int N = text.size();
// Stores length of pattern
int M = pattern.size();
// dp[i][j]: Check if { text[0], .. text[i] }
// matches {pattern[0], ... pattern[j]} or not
vector<vector<bool>> dp(N + 1, vector<bool>(M + 1, false));
// Base Case
dp[0][0] = true;
// Iterate over the characters
// of the string pattern
for (int i = 0; i < M; i++)
{
if (pattern[i] == '*'
&& dp[0][i - 1]) {
// Update dp[0][i + 1]
dp[0][i + 1] = true;
}
}
// Iterate over the characters
// of both the strings
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
// If current character
// in the pattern is '.'
if (pattern[j] == '.') {
// Update dp[i + 1][j + 1]
dp[i + 1][j + 1] = dp[i][j];
}
// If current character in
// both the strings are equal
if (pattern[j]
== text[i]) {
// Update dp[i + 1][j + 1]
dp[i + 1][j + 1] = dp[i][j];
}
// If current character
// in the pattern is '*'
if (pattern[j] == '*') {
if (pattern[j - 1] != text[i]
&& pattern[j - 1] != '.') {
// Update dp[i + 1][j + 1]
dp[i + 1][j + 1] = dp[i + 1][j - 1];
}
else {
// Update dp[i+1][j+1]
dp[i + 1][j + 1] = (dp[i + 1][j]
or dp[i][j + 1]
or dp[i + 1][j - 1]);
}
}
}
}
// Return dp[M][N]
return dp[N][M];
}
// Driver Code
int main()
{
string text = "geeksforgeeks";
string pattern = "ge*ksforgeeks";
if (isMatch(text, pattern))
cout<<"Yes";
else
cout<<"No";
}
// This code is contributed by mohiy kumar 29.
Java
// Java program for the above approach
import java.io.*;
class GFG {
// Function to check if the pattern
// consisting of '*', '.' and lowercase
// characters matches the text or not
static boolean isMatch(String text,
String pattern)
{
// Base Case
if (text == null || pattern == null) {
return false;
}
// Stores length of text
int N = text.length();
// Stores length of pattern
int M = pattern.length();
// dp[i][j]: Check if { text[0], .. text[i] }
// matches {pattern[0], ... pattern[j]} or not
boolean[][] dp = new boolean[N + 1][M + 1];
// Base Case
dp[0][0] = true;
// Iterate over the characters
// of the string pattern
for (int i = 0; i < M; i++) {
if (pattern.charAt(i) == '*'
&& dp[0][i - 1]) {
// Update dp[0][i + 1]
dp[0][i + 1] = true;
}
}
// Iterate over the characters
// of both the strings
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
// If current character
// in the pattern is '.'
if (pattern.charAt(j) == '.') {
// Update dp[i + 1][j + 1]
dp[i + 1][j + 1] = dp[i][j];
}
// If current character in
// both the strings are equal
if (pattern.charAt(j)
== text.charAt(i)) {
// Update dp[i + 1][j + 1]
dp[i + 1][j + 1] = dp[i][j];
}
// If current character
// in the pattern is '*'
if (pattern.charAt(j) == '*') {
if (pattern.charAt(j - 1) != text.charAt(i)
&& pattern.charAt(j - 1) != '.') {
// Update dp[i + 1][j + 1]
dp[i + 1][j + 1] = dp[i + 1][j - 1];
}
else {
// Update dp[i+1][j+1]
dp[i + 1][j + 1] = (dp[i + 1][j]
|| dp[i][j + 1]
|| dp[i + 1][j - 1]);
}
}
}
}
// Return dp[M][N]
return dp[N][M];
}
// Driver Code
public static void main(String[] args)
{
String text = "geeksforgeeks";
String pattern = "ge*ksforgeeks";
if (isMatch(text, pattern)) {
System.out.println("Yes");
}
else {
System.out.println("No");
}
}
}
Python3
# Python3 program for the above approach
import numpy as np
# Function to check if the pattern
# consisting of '*', '.' and lowercase
# characters matches the text or not
def isMatch(text, pattern):
# Base Case
if (text == "" or pattern == ""):
return False
# Stores length of text
N = len(text)
# Stores length of pattern
M = len(pattern)
# dp[i][j]: Check if { text[0], .. text[i] }
# matches {pattern[0], ... pattern[j]} or not
dp = np.zeros((N + 1, M + 1))
# Base Case
dp[0][0] = True
# Iterate over the characters
# of the string pattern
for i in range(M):
if (pattern[i] == '*' and dp[0][i - 1]):
# Update dp[0][i + 1]
dp[0][i + 1] = True
# Iterate over the characters
# of both the strings
for i in range(N):
for j in range(M):
# If current character
# in the pattern is '.'
if (pattern[j] == '.'):
# Update dp[i + 1][j + 1]
dp[i + 1][j + 1] = dp[i][j]
# If current character in
# both the strings are equal
if (pattern[j] == text[i]):
# Update dp[i + 1][j + 1]
dp[i + 1][j + 1] = dp[i][j]
# If current character
# in the pattern is '*'
if (pattern[j] == '*'):
if (pattern[j - 1] != text[i] and
pattern[j - 1] != '.'):
# Update dp[i + 1][j + 1]
dp[i + 1][j + 1] = dp[i + 1][j - 1]
else:
# Update dp[i+1][j+1]
dp[i + 1][j + 1] = (dp[i + 1][j] or
dp[i][j + 1] or
dp[i + 1][j - 1])
# Return dp[M][N]
return dp[N][M]
# Driver Code
if __name__ == "__main__" :
text = "geeksforgeeks"
pattern = "ge*ksforgeeks"
if (isMatch(text, pattern)):
print("Yes")
else:
print("No")
# This code is contributed by AnkThon
C#
// C# program for the above approach
using System;
class GFG{
// Function to check if the pattern
// consisting of '*', '.' and lowercase
// characters matches the text or not
static bool isMatch(string text, string pattern)
{
// Base Case
if (text == null || pattern == null)
{
return false;
}
// Stores length of text
int N = text.Length;
// Stores length of pattern
int M = pattern.Length;
// dp[i][j]: Check if { text[0], .. text[i] }
// matches {pattern[0], ... pattern[j]} or not
bool[,] dp = new bool[N + 1, M + 1];
// Base Case
dp[0, 0] = true;
// Iterate over the characters
// of the string pattern
for(int i = 0; i < M; i++)
{
if (pattern[i] == '*' && dp[0, i - 1])
{
// Update dp[0][i + 1]
dp[0, i + 1] = true;
}
}
// Iterate over the characters
// of both the strings
for(int i = 0; i < N; i++)
{
for(int j = 0; j < M; j++)
{
// If current character
// in the pattern is '.'
if (pattern[j] == '.')
{
// Update dp[i + 1][j + 1]
dp[i + 1, j + 1] = dp[i, j];
}
// If current character in
// both the strings are equal
if (pattern[j] == text[i])
{
// Update dp[i + 1][j + 1]
dp[i + 1, j + 1] = dp[i, j];
}
// If current character
// in the pattern is '*'
if (pattern[j] == '*')
{
if (pattern[j - 1] != text[i] &&
pattern[j - 1] != '.')
{
// Update dp[i + 1][j + 1]
dp[i + 1, j + 1] = dp[i + 1, j - 1];
}
else
{
// Update dp[i+1][j+1]
dp[i + 1, j + 1] = (dp[i + 1, j] ||
dp[i, j + 1] ||
dp[i + 1, j - 1]);
}
}
}
}
// Return dp[M][N]
return dp[N, M];
}
// Driver Code
public static void Main()
{
string text = "geeksforgeeks";
string pattern = "ge*ksforgeeks";
if (isMatch(text, pattern))
{
Console.WriteLine("Yes");
}
else
{
Console.WriteLine("No");
}
}
}
// This code is contributed by ukasp
Javascript
<script>
// JavaScript program for the above approach
// Function to check if the pattern
// consisting of '*', '.' and lowercase
// characters matches the text or not
function isMatch(text, pattern)
{
// Base Case
if (text == null || pattern == null) {
return false;
}
// Stores length of text
let N = text.length;
// Stores length of pattern
let M = pattern.length;
// dp[i][j]: Check if { text[0], .. text[i] }
// matches {pattern[0], ... pattern[j]} or not
let dp = new Array(N + 1);
for (let i = 0; i <= N; i++)
{
dp[i] = new Array(M + 1);
for (let j = 0; j <= M; j++)
{
dp[i][j] = false;
}
}
// Base Case
dp[0][0] = true;
// Iterate over the characters
// of the string pattern
for (let i = 0; i < M; i++) {
if (pattern[i] == '*'
&& dp[0][i - 1]) {
// Update dp[0][i + 1]
dp[0][i + 1] = true;
}
}
// Iterate over the characters
// of both the strings
for (let i = 0; i < N; i++) {
for (let j = 0; j < M; j++) {
// If current character
// in the pattern is '.'
if (pattern[j] == '.') {
// Update dp[i + 1][j + 1]
dp[i + 1][j + 1] = dp[i][j];
}
// If current character in
// both the strings are equal
if (pattern[j] == text[i]) {
// Update dp[i + 1][j + 1]
dp[i + 1][j + 1] = dp[i][j];
}
// If current character
// in the pattern is '*'
if (pattern[j] == '*') {
if (pattern[j - 1] != text[i]
&& pattern[j - 1] != '.') {
// Update dp[i + 1][j + 1]
dp[i + 1][j + 1] = dp[i + 1][j - 1];
}
else {
// Update dp[i+1][j+1]
dp[i + 1][j + 1] = (dp[i + 1][j]
|| dp[i][j + 1]
|| dp[i + 1][j - 1]);
}
}
}
}
// Return dp[M][N]
return dp[N][M];
}
let text = "geeksforgeeks";
let pattern = "ge*ksforgeeks";
if (isMatch(text, pattern)) {
document.write("Yes");
}
else {
document.write("No");
}
</script>
Producción:
Yes
Complejidad de Tiempo: O(M * N)
Espacio Auxiliar: O(M * N)
Publicación traducida automáticamente
Artículo escrito por kalyansuman y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA