Dada una string S de longitud L , donde L es un cuadrado perfecto , la tarea es comprobar si la string dada cumple las siguientes condiciones:
- Inserte los caracteres de la string en una array cuadrada A[][] de dimensiones √L x √L en filas.
- Inicialice otra array M[][] con 0 s. Rellena la diagonal izquierda con 1 . Ahora, para 1 presente en la diagonal izquierda, llena su correspondiente diagonal derecha con 1 s.
- Ahora, verifique si todos los índices en la array M[][] que contiene 1 , contienen el mismo carácter en A[][] .
Si se cumple la condición, escriba “Sí”. De lo contrario, escriba “No” .
Ejemplos:
Entrada: S = ”abacdaeaafaghaia”
Salida: Sí
Explicación:
Entrada: S = ”abacdaeabfaghaia”
Salida: No
Enfoque: La idea es atravesar la array A[][] donde su carácter correspondiente en la array M[][] es 1 . Siga los pasos a continuación para resolver el problema:
- Calcula las dimensiones de la array como N = √L .
- Iterar sobre la diagonal izquierda visitando cada celda, A[i][i] donde 1<= i<= N .
- Para cada elemento de la diagonal izquierda en la celda A[i][i] , inicialice las variables x e y con i y recorra su diagonal derecha correspondiente visitando el carácter S[x*N + y] y S[y*N + x ] y disminuya x cada vez en 1 e incremente y cada vez en 1 para moverse a lo largo de las siguientes celdas en las diagonales derechas, mientras que x no es menor que 0 e y es menor que N .
- Si se encuentra que todos los caracteres son iguales en el paso anterior, imprima «Sí» . De lo contrario, imprima «No» si se encuentra alguna discrepancia.
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 given string
// satisfies the given conditions
void isValid(string s)
{
// Dimensions
int n = sqrt(s.length());
char check = s[0];
// Left diagonal
for (int i = 0; i < n; i++) {
int x = i, y = i;
// Right diagonal
while (x >= 0 && y < n) {
if (s[(n * x) + y] != check
|| s[(n * y) + x] != check) {
// Conditions not satisfied
cout << "No" << endl;
return;
}
x--;
y++;
}
}
// Print Yes
cout << "Yes" << endl;
}
// Driver Code
int main()
{
// Given String
string str = "abacdaeaafaghaia";
// Function call
isValid(str);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Function to check if given string
// satisfies the given conditions
static void isValid(String s)
{
// Dimensions
int n = (int)Math.sqrt(s.length());
char check = s.charAt(0);
// Left diagonal
for(int i = 0; i < n; i++)
{
int x = i, y = i;
// Right diagonal
while (x >= 0 && y < n)
{
if (s.charAt((n * x) + y) != check ||
s.charAt((n * y) + x) != check)
{
// Conditions not satisfied
System.out.print("No");
return;
}
x--;
y++;
}
}
// Print Yes
System.out.print("Yes");
}
// Driver Code
public static void main(String[] args)
{
// Given String
String str = "abacdaeaafaghaia";
// Function call
isValid(str);
}
}
// This code is contributed by code_hunt
Python3
# Python3 program for the above approach
import math
# Function to check if given string
# satisfies the given conditions
def isValid(s):
# Dimensions
n = int(math.sqrt(len(s)))
check = s[0]
# Left diagonal
for i in range(n):
x = i
y = i
# Right diagonal
while (x >= 0 and y < n):
if (s[n * x + y] != check or
s[n * x + x] != check):
# Conditions not satisfied
print("No")
return
x -= 1
y += 1
# Print Yes
print("Yes")
# Driver Code
# Given String
str = "abacdaeaafaghaia"
# Function call
isValid(str)
# This code is contributed by avanitrachhadiya2155
C#
// C# program for the above approach
using System;
class GFG{
// Function to check if given string
// satisfies the given conditions
static void isValid(string s)
{
// Dimensions
int n = (int)Math.Sqrt(s.Length);
char check = s[0];
// Left diagonal
for(int i = 0; i < n; i++)
{
int x = i, y = i;
// Right diagonal
while (x >= 0 && y < n)
{
if (s[(n * x) + y] != check ||
s[(n * y) + x] != check)
{
// Conditions not satisfied
Console.Write("No");
return;
}
x--;
y++;
}
}
// Print Yes
Console.Write("Yes");
}
// Driver code
public static void Main()
{
// Given String
string str = "abacdaeaafaghaia";
// Function call
isValid(str);
}
}
// This code is contributed by sanjoy_62
Javascript
<script>
// Javascript program to implement
// the above approach
// Function to check if given string
// satisfies the given conditions
function isValid(s)
{
// Dimensions
let n = Math.sqrt(s.length);
let check = s[0];
// Left diagonal
for(let i = 0; i < n; i++)
{
let x = i, y = i;
// Right diagonal
while (x >= 0 && y < n)
{
if (s[(n * x) + y]!= check ||
s[(n * y) + x] != check)
{
// Conditions not satisfied
document.write("No");
return;
}
x--;
y++;
}
}
// Print Yes
document.write("Yes");
}
// Driver Code
// Given String
let str = "abacdaeaafaghaia";
// Function call
isValid(str);
// This code is contributed by souravghosh0416.
</script>
Producción:
Yes
Complejidad de tiempo: O(L) donde L es la longitud de la string dada.
Espacio Auxiliar: O(L)