Dada una string str y consultas Q. Cada consulta consta de dos números L y R . La tarea es imprimir si la substring [L…R] es palíndromo o no.
Ejemplos:
Entrada: str = “abacccde”, Q[][] = {{0, 2}, {1, 2}, {2, 4}, {3, 5}}
Salida:
Sí
No
No
SíEntrada: str = “abaaab”, Q[][] = {{0, 1}, {1, 5}}
Salida:
No
Sí
Enfoque simple : un enfoque ingenuo es verificar cada substring si es palíndromo o no. En el peor de los casos, cada consulta puede tomar hasta O(Q) .
Enfoque eficiente : un enfoque eficiente es utilizar la programación dinámica para resolver el problema anterior. Inicialmente podemos crear la tabla DP que almacena si la substring [i….j] es palíndromo o no. Mantenemos un booleano dp[n][n] que se llena de forma ascendente. El valor de dp[i][j] es verdadero si la substring es un palíndromo; de lo contrario, es falso. Para calcular dp[i][j], primero verificamos el valor de dp[i+1][j-1] , si el valor es verdadero y s[i] es el mismo que s[j] , entonces hacemos dp[i][j] verdadero. De lo contrario, el valor de dp[i][j] se hace falso.
Ahora, para cada consulta, verifique si dp[l][r]es cierto o no.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
#define N 100
// Pre-processing function
void pre_process(bool dp[N][N], string s)
{
// Get the size of the string
int n = s.size();
// Initially mark every
// position as false
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++)
dp[i][j] = false;
}
// For the length
for (int j = 1; j <= n; j++) {
// Iterate for every index with
// length j
for (int i = 0; i <= n - j; i++) {
// If the length is less than 2
if (j <= 2) {
// If characters are equal
if (s[i] == s[i + j - 1])
dp[i][i + j - 1] = true;
}
// Check for equal
else if (s[i] == s[i + j - 1])
dp[i][i + j - 1] = dp[i + 1][i + j - 2];
}
}
}
// Function to answer every query in O(1)
void answerQuery(int l, int r, bool dp[N][N])
{
if (dp[l][r])
cout << "Yes\n";
else
cout << "No\n";
}
// Driver code
int main()
{
string s = "abaaab";
bool dp[N][N];
pre_process(dp, s);
int queries[][2] = { { 0, 1 }, { 1, 5 } };
int q = sizeof(queries) / sizeof(queries[0]);
for (int i = 0; i < q; i++)
answerQuery(queries[i][0], queries[i][1], dp);
return 0;
}
Java
// Java implementation of the approach
class GFG {
static int N = 100;
// Pre-processing function
static void pre_process(boolean dp[][], char[] s)
{
// Get the size of the string
int n = s.length;
// Initially mark every
// position as false
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
dp[i][j] = false;
}
}
// For the length
for (int j = 1; j <= n; j++) {
// Iterate for every index with
// length j
for (int i = 0; i <= n - j; i++) {
// If the length is less than 2
if (j <= 2) {
// If characters are equal
if (s[i] == s[i + j - 1]) {
dp[i][i + j - 1] = true;
}
}
// Check for equal
else if (s[i] == s[i + j - 1]) {
dp[i][i + j - 1] = dp[i + 1][i + j - 2];
}
}
}
}
// Function to answer every query in O(1)
static void answerQuery(int l, int r, boolean dp[][])
{
if (dp[l][r]) {
System.out.println("Yes");
}
else {
System.out.println("No");
}
}
// Driver code
public static void main(String[] args)
{
String s = "abaaab";
boolean[][] dp = new boolean[N][N];
pre_process(dp, s.toCharArray());
int queries[][] = { { 0, 1 }, { 1, 5 } };
int q = queries.length;
for (int i = 0; i < q; i++) {
answerQuery(queries[i][0], queries[i][1], dp);
}
}
}
// This code contributed by Rajput-Ji
Python3
# Python3 implementation of the approach
N = 100
# Pre-processing function
def pre_process(dp, s):
# Get the size of the string
n = len(s)
# Initially mark every
# position as false
for i in range(n):
for j in range(n):
dp[i][j] = False
# For the length
for j in range(1, n + 1):
# Iterate for every index with
# length j
for i in range(n - j + 1):
# If the length is less than 2
if (j <= 2):
# If characters are equal
if (s[i] == s[i + j - 1]):
dp[i][i + j - 1] = True
# Check for equal
elif (s[i] == s[i + j - 1]):
dp[i][i + j - 1] = dp[i + 1][i + j - 2]
# Function to answer every query in O(1)
def answerQuery(l, r, dp):
if (dp[l][r]):
print("Yes")
else:
print("No")
# Driver code
s = "abaaab"
dp = [[0 for i in range(N)]
for i in range(N)]
pre_process(dp, s)
queries = [[0, 1], [1, 5]]
q = len(queries)
for i in range(q):
answerQuery(queries[i][0],
queries[i][1], dp)
# This code is contributed by mohit kumar
C#
// C# implementation of the approach
using System;
class GFG {
static int N = 100;
// Pre-processing function
static void pre_process(bool[, ] dp, char[] s)
{
// Get the size of the string
int n = s.Length;
// Initially mark every
// position as false
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
dp[i, j] = false;
}
}
// For the length
for (int j = 1; j <= n; j++) {
// Iterate for every index with
// length j
for (int i = 0; i <= n - j; i++) {
// If the length is less than 2
if (j <= 2) {
// If characters are equal
if (s[i] == s[i + j - 1]) {
dp[i, i + j - 1] = true;
}
}
// Check for equal
else if (s[i] == s[i + j - 1]) {
dp[i, i + j - 1] = dp[i + 1, i + j - 2];
}
}
}
}
// Function to answer every query in O(1)
static void answerQuery(int l, int r, bool[, ] dp)
{
if (dp[l, r]) {
Console.WriteLine("Yes");
}
else {
Console.WriteLine("No");
}
}
// Driver code
public static void Main()
{
string s = "abaaab";
bool[, ] dp = new bool[N, N];
pre_process(dp, s.ToCharArray());
int[, ] queries = { { 0, 1 }, { 1, 5 } };
int q = queries.Length;
for (int i = 0; i < q; i++) {
answerQuery(queries[i, 0], queries[i, 1], dp);
}
}
}
// This code is contributed by Ankit.
PHP
<?php
// PHP implementation of the approach
$N = 100;
// Pre-processing function
function pre_process($dp, $s)
{
// Get the size of the string
$n = strlen($s);
// Initially mark every
// position as false
for ($i = 0; $i < $n; $i++)
{
for ($j = 0; $j < $n; $j++)
$dp[$i][$j] = false;
}
// For the length
for ($j = 1; $j <= $n; $j++)
{
// Iterate for every index with
// length j
for ($i = 0; $i <= $n - $j; $i++)
{
// If the length is less than 2
if ($j <= 2)
{
// If characters are equal
if ($s[$i] == $s[$i + $j - 1])
$dp[$i][$i + $j - 1] = true;
}
// Check for equal
else if ($s[$i] == $s[$i + $j - 1])
$dp[$i][$i + $j - 1] = $dp[$i + 1][$i + $j - 2];
}
}
return $dp;
}
// Function to answer every query in O(1)
function answerQuery($l, $r, $dp)
{
if ($dp[$l][$r])
echo "Yes\n";
else
echo "No\n";
}
// Driver code
$s = "abaaab";
$dp = array(array());
$dp = pre_process($dp, $s);
$queries = array(array(0, 1),
array(1, 5));
$q = count($queries);
for ($i = 0; $i < $q; $i++)
answerQuery($queries[$i][0],
$queries[$i][1], $dp);
// This code is contributed by Ryuga
?>
Javascript
<script>
// javascript implementation of the approach
var N = 100;
// Pre-processing function
function pre_process( dp, s) {
// Get the size of the string
var n = s.length;
// Initially mark every
// position as false
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
dp[i][j] = false;
}
}
// For the length
for (j = 1; j <= n; j++) {
// Iterate for every index with
// length j
for (i = 0; i <= n - j; i++) {
// If the length is less than 2
if (j <= 2) {
// If characters are equal
if (s[i] == s[i + j - 1]) {
dp[i][i + j - 1] = true;
}
}
// Check for equal
else if (s[i] == s[i + j - 1]) {
dp[i][i + j - 1] = dp[i + 1][i + j - 2];
}
}
}
}
// Function to answer every query in O(1)
function answerQuery(l , r, dp) {
if (dp[l][r]) {
document.write("Yes<br/>");
}
else {
document.write("No<br/>");
}
}
// Driver code
var s = "abaaab";
var dp = Array(N).fill().map(()=>Array(N).fill());
pre_process(dp, s);
var queries = [ [ 0, 1 ], [ 1, 5 ] ];
var q = queries.length;
for (i = 0; i < q; i++) {
answerQuery(queries[i][0], queries[i][1], dp);
}
// This code contributed by Rajput-Ji
</script>
Producción:
No Yes
Complejidad de tiempo: O (N * N), ya que estamos usando bucles anidados para atravesar N * N veces. Donde N es la longitud de la string.
Espacio auxiliar: O(N*N), ya que estamos usando espacio adicional para la array dp.