LeetCode – Palabras expresivas (Java)

A veces, las personas repiten letras para representar un sentimiento adicional, como «hola» -> «heeellooo», «hola» -> «hiiii». En estas cadenas como «heeellooo», tenemos grupos de letras adyacentes que son todas iguales: «h», «eee», «ll», «ooo».

Para alguna cadena dada S, una palabra de consulta es elástica si se puede hacer que sea igual a S mediante cualquier número de aplicaciones de la siguiente operación de extensión: elija un grupo que consta de caracteres c, y agregue algún número de caracteres c al grupo de modo que el tamaño del grupo sea 3 o más.

Por ejemplo, comenzando con «hola», podríamos hacer una extensión en el grupo «o» para obtener «holaoo», pero no podemos obtener «hola» ya que el grupo «oo» tiene un tamaño menor que 3. Además, podríamos hacer otra extensión como «ll» -> «lllll» para obtener «helllllooo». Si S = «helllllooo», entonces la palabra de consulta «hello» sería elástica debido a estas dos operaciones de extensión: query = «hello» -> «hellooo» -> «helllllooo» = S.

Dada una lista de palabras de consulta, devuelve el número de palabras elásticas.

Ejemplo:
Aporte:
S = «heeellooo»
palabras = [«hello», «hi», «helo»]

Salida: 1
Explicación:
Podemos extender «e» y «o» en la palabra «hola» para obtener «heeellooo».
No podemos extender «helo» para obtener «heeellooo» porque el grupo «ll» no es de tamaño 3 o más.

Solución Java

Este problema es similar a la coincidencia de expresiones regulares.

public int expressiveWords(String S, String[] words) {
    int count = 0;
    for (String s : words) {
        if (isMatch(S, 0, s, 0)) {
            count++;
        }
    }
 
    return count;
}
 
private boolean isMatch(String s1, int i, String s2, int j) {
    if (i >= s1.length() && j >= s2.length()) {
        return true;
    } else if (i >= s1.length() || j >= s2.length()) {
        return false;
    }
 
    if (s1.charAt(i) != s2.charAt(j)) {
        return false;
    }
 
    boolean res = false;
 
    if (i + 2 < s1.length()
            && s1.charAt(i + 1) == s2.charAt(j)
            && s1.charAt(i + 2) == s2.charAt(j)) {
        int m = i + 2;
        int n = j + 1;
        while (m < s1.length() && s1.charAt(m) == s2.charAt(j)) {
            m++;
        }
        while (n < s2.length() && s2.charAt(n) == s2.charAt(n - 1)) {
            n++;
        }
        if (n - j > m - i) {
            return false;
        }
 
        res = isMatch(s1, m, s2, n);
    }
 
    res = res | isMatch(s1, i + 1, s2, j + 1);
 
    return res;
}