LeetCode – Coincidencia de expresiones regulares (Java)

Implemente la coincidencia de expresiones regulares con soporte para ‘.’ y ‘*’.

‘.’ Coincide con cualquier carácter individual.
‘*’ Coincide con cero o más del elemento anterior.

La coincidencia debe cubrir toda la cadena de entrada (no parcial).

El prototipo de función debe ser:
bool isMatch (const char * s, const char * p)

Algunos ejemplos:
isMatch («aa», «a») devuelve falso
isMatch («aa», «aa») devuelve verdadero
isMatch («aaa», «aa») devuelve falso
isMatch («aa», «a *») devuelve verdadero
isMatch («aa», «. *») devuelve verdadero
isMatch («ab», «. *») devuelve verdadero
isMatch («aab», «c * a * b») devuelve verdadero

1. Análisis

En primer lugar, este es uno de los problemas de mayor dificultad. Es difícil pensar en todos los casos diferentes. El problema debe simplificarse para manejar 2 casos básicos:

el segundo carácter del patrón es «*»
el segundo carácter del patrón no es «*»

Para el primer caso, si el primer carácter del patrón no es «.», El primer carácter del patrón y la cadena deben ser iguales. Luego continúe haciendo coincidir la parte restante.

Para el segundo caso, si el primer carácter del patrón es «.» o el primer carácter del patrón == el primer carácter i de la cadena, continúe haciendo coincidir la parte restante.

2. Solución Java 1 (breve)

Se acepta la siguiente solución de Java.

public class Solution {
    public boolean isMatch(String s, String p) {
 
        if(p.length() == 0)
            return s.length() == 0;
 
        //p's length 1 is special case    
        if(p.length() == 1 || p.charAt(1) != '*'){
            if(s.length() < 1 || (p.charAt(0) != '.' && s.charAt(0) != p.charAt(0)))
                return false;
            return isMatch(s.substring(1), p.substring(1));    
 
        }else{
            int len = s.length();
 
            int i = -1; 
            while(i<len && (i < 0 || p.charAt(0) == '.' || p.charAt(0) == s.charAt(i))){
                if(isMatch(s.substring(i+1), p.substring(2)))
                    return true;
                i++;
            }
            return false;
        } 
    }
}

LeetCode - Cadenas isomórficas (Java)

3. Java Solution 2 (más legible)

public boolean isMatch(String s, String p) {
	// base case
	if (p.length() == 0) {
		return s.length() == 0;
	}
 
	// special case
	if (p.length() == 1) {
 
		// if the length of s is 0, return false
		if (s.length() < 1) {
			return false;
		}
 
		//if the first does not match, return false
		else if ((p.charAt(0) != s.charAt(0)) && (p.charAt(0) != '.')) {
			return false;
		}
 
		// otherwise, compare the rest of the string of s and p.
		else {
			return isMatch(s.substring(1), p.substring(1));
		}
	}
 
	// case 1: when the second char of p is not '*'
	if (p.charAt(1) != '*') {
		if (s.length() < 1) {
			return false;
		}
		if ((p.charAt(0) != s.charAt(0)) && (p.charAt(0) != '.')) {
			return false;
		} else {
			return isMatch(s.substring(1), p.substring(1));
		}
	}
 
	// case 2: when the second char of p is '*', complex case.
	else {
		//case 2.1: a char & '*' can stand for 0 element
		if (isMatch(s, p.substring(2))) {
			return true;
		}
 
		//case 2.2: a char & '*' can stand for 1 or more preceding element, 
		//so try every sub string
		int i = 0;
		while (i<s.length() && (s.charAt(i)==p.charAt(0) || p.charAt(0)=='.')){
			if (isMatch(s.substring(i + 1), p.substring(2))) {
				return true;
			}
			i++;
		}
		return false;
	}
}

LeetCode: la mayoría de las piedras se eliminan con la misma fila o columna (Java)

Solución Java 3: uso del índice

También podemos agregar un método auxiliar para usar el índice, en lugar de pasar subcadenas de forma recursiva.

public boolean isMatch(String s, String p) {
    return helper(s, p, 0, 0);
}
 
private boolean helper(String s, String p, int i, int j) {
    if (i >= s.length() && j >= p.length()) {
        return true;
    }
 
 
    if (j < p.length() - 1 && p.charAt(j + 1) == '*') {
        if (helper(s, p, i, j + 2)) {
            return true;
        }
 
        if (p.charAt(j) == '.') {
            for (int k = i; k < s.length(); k++) {
                if (helper(s, p, k + 1, j + 2)) {
                    return true;
                }
            }
        } else {
            for (int k = i; k < s.length(); k++) {
                if (s.charAt(k) == p.charAt(j)) {
                    if (helper(s, p, k + 1, j + 2)) {
                        return true;
                    }
                } else {
                    break;
                }
            }
        }
    } else if (i < s.length() && j < p.length() && (s.charAt(i) == p.charAt(j) || p.charAt(j) == '.')) {
        return helper(s, p, i + 1, j + 1);
    }
 
    return false;
}

LeetCode - Lista de reorden (Java)

Artículos Relacionados:

Por Programación.Click

Deja una respuesta Cancelar la respuesta