LeetCode – Total de subsecuencias distintas (Java)

Dada una cadena S y una cadena T, cuente el número de subsecuencias distintas de T en S.

Una subsecuencia de una cadena es una nueva cadena que se forma a partir de la cadena original eliminando algunos (puede ser ninguno) de los caracteres sin alterar las posiciones relativas de los caracteres restantes. (es decir, «ACE» es una subsecuencia de «ABCDE» mientras que «AEC» no lo es).

Aquí hay un ejemplo:
S = «conejo», T = «conejo»

Regresar 3.

Análisis

El problema en sí es muy difícil de comprender. Se puede afirmar así:
Da una secuencia S y T, ¿cuántas subsecuencias distintas de S equivalen a T?
¿Cómo se define la subsecuencia «distinta»? Claramente, lo ‘distinto’ aquí significa una combinación de operación diferente, no la cadena final de la subsecuencia. De lo contrario, el resultado es siempre 0 o 1. – del comentario de Jason

Cuando vea un problema de cadena relacionado con la subsecuencia o coincidencia, el método de programación dinámica debería venir a la mente de forma natural. La clave es encontrar la condición inicial y cambiante.

Solución Java 1

Sea W (i, j) el número de subsecuencias de S (0, i) igual a T (0, j). Si S.charAt (i) == T.charAt (j), W (i, j) = W (i-1, j-1) + W (i-1, j); De lo contrario, W (i, j) = W (i-1, j).

public int numDistincts(String S, String T) {
	int[][] table = new int[S.length() + 1][T.length() + 1];
 
	for (int i = 0; i < S.length(); i++)
		table[i][0] = 1;
 
	for (int i = 1; i <= S.length(); i++) {
		for (int j = 1; j <= T.length(); j++) {
			if (S.charAt(i - 1) == T.charAt(j - 1)) {
				table[i][j] += table[i - 1][j] + table[i - 1][j - 1];
			} else {
				table[i][j] += table[i - 1][j];
			}
		}
	}
 
	return table[S.length()][T.length()];
}

Solución Java 2

NO escriba algo como esto, aunque también puede pasar el juez en línea.

public int numDistinct(String S, String T) {
	HashMap<Character, ArrayList<Integer>> map = new HashMap<Character, ArrayList<Integer>>();
 
	for (int i = 0; i < T.length(); i++) {
		if (map.containsKey(T.charAt(i))) {
			map.get(T.charAt(i)).add(i);
		} else {
			ArrayList<Integer> temp = new ArrayList<Integer>();
			temp.add(i);
			map.put(T.charAt(i), temp);
		}
	}
 
	int[] result = new int[T.length() + 1];
	result[0] = 1;
 
	for (int i = 0; i < S.length(); i++) {
		char c = S.charAt(i);
 
		if (map.containsKey(c)) {
			ArrayList<Integer> temp = map.get(c);
			int[] old = new int[temp.size()];
 
			for (int j = 0; j < temp.size(); j++)
				old[j] = result[temp.get(j)];
 
			// the relation
			for (int j = 0; j < temp.size(); j++)
				result[temp.get(j) + 1] = result[temp.get(j) + 1] + old[j];
		}
	}
 
	return result[T.length()];
}