Dada una string str y un par de caracteres K , la tarea es verificar si la string str puede convertirse en palíndromo , reemplazando un carácter de cada par con el otro.
Ejemplos:
Entrada: str = “geeks”, K = 2, pares = [[“g”, “s”], [“k”, “e”]]
Salida : Verdadero
Explicación:
Intercambiar ‘s’ de “geeks” con ‘ g’ usando par [‘g’, ‘s’] = “geekg”
Intercambiar ‘k’ de “geekg” con ‘e’ usando par [‘k’, ‘e’] = “geeeg”
Ahora la string resultante es una palíndromo. Por lo tanto, la salida será True.Entrada : str = “geeks”, K = 1, pares = [[“g”, “s”]]
Salida: Falso
Explicación: Aquí solo se puede intercambiar el primer carácter (g, s)
La string final formada será: geekg , que no es un palíndromo.
Enfoque ingenuo : el problema dado se puede resolver creando un gráfico no dirigido donde un borde que conecta (x, y) representa una relación entre los caracteres x e y.
- Verifique la condición del palíndromo validando los primeros semicaracteres con los semicaracteres posteriores.
- Si no es igual:
- Ejecute un dfs desde el primer carácter y verifique si se puede alcanzar el último carácter.
- Luego, verifique el segundo carácter con el penúltimo carácter y así sucesivamente.
Complejidad de tiempo: O(N * M), donde N es el tamaño de la string objetivo y M es el tamaño de la array de pares
Espacio auxiliar: O(1)
Enfoque eficiente: el problema se puede resolver de manera eficiente con la ayuda de la siguiente idea:
Utilice una estructura de datos de conjuntos disjuntos donde cada par [i][0] y par [i][1] se puedan unir bajo el mismo conjunto y la operación de búsqueda se pueda realizar de manera eficiente.
En lugar de buscar los caracteres cada vez, intente agrupar todos los caracteres que están conectados directa o indirectamente en el mismo conjunto.
A continuación se muestra la implementación del enfoque anterior:
C++
#include <iostream>
#include <string>
#include <vector>
using namespace std;
// Structure for Disjoint set union
struct disjoint_set {
vector<int> parent, rank;
// Initialize DSU variables
disjoint_set()
{
parent.resize(26);
rank.resize(26);
for (int i = 0 ; i < 26 ; i++) {
parent[i] = i;
rank[i] = 1;
}
}
// Find parent of vertex 'v'
int find_parent(int v)
{
if (v == parent[v])
return v;
return parent[v] = find_parent(parent[v]);
}
// Union two sets containing vertices a and b
void Union(int p1, int p2)
{
p1 = find_parent(p1);
p2 = find_parent(p2);
if (p1 != p2){
// rank of p1 smaller than p2
if(rank[p1] < rank[p2]){
parent[p1] = p2;
}else if(rank[p2] < rank[p1]){
parent[p2] = p1;
// rank of p2 equal to p1
}else{
parent[p2] = p1;
rank[p1] += 1;
}
}
}
// Function for checking whether
// vertex a and b are in same set or not
bool connected(int p1, int p2)
{
p1 = find_parent(p1);
p2 = find_parent(p2);
if(p1 == p2) return true;
return false;
}
};
// Function solving the problem
bool solve(string& target, vector<pair<char, char> >& pairs)
{
// Initialize new instance of DSU
disjoint_set dsu; // Only lowercase letters
for (auto i : pairs) {
dsu.Union(i.first - 'a', i.second - 'a');
}
int lower = 0, upper = (int)target.length() - 1;
while (lower <= upper) {
if (!dsu.connected(target[lower] - 'a', target[upper] - 'a')) {
return false;
}
lower+=1;
upper-=1;
}
return true;
}
// Driver code
int main()
{
string target = "geeks";
vector<pair<char, char> > pairs
= { { 'g', 's' }, { 'e', 'k' } };
bool ans = solve(target, pairs);
if (ans) {
cout << "true\n";
}
else {
cout << "false\n";
}
return 0;
}
// This code is contributed by subhamgoyal2014.
Python3
# Python code for the above approach:
class disjoint_set():
def __init__(self):
# string consist of only smallcase letters
self.parent = [i for i in range(26)]
self.rank = [1 for i in range(26)]
def find_parent(self, x):
if (self.parent[x] == x):
return x
self.parent[x] = self.find_parent(self.parent[x])
return (self.parent[x])
def union(self, u, v):
p1 = self.find_parent(u)
p2 = self.find_parent(v)
if (p1 != p2):
# rank of p1 smaller than p2
if(self.rank[p1] < self.rank[p2]):
self.parent[p1] = p2
elif(self.rank[p2] < self.rank[p1]):
self.parent[p2] = p1
# rank of p2 equal to p1
else:
self.parent[p2] = p1
self.rank[p1] += 1
def connected(self, w1, w2):
p1 = self.find_parent(w1)
p2 = self.find_parent(w2)
if (p1 == p2):
return True
return False
class Solution:
def solve(self, target, pairs):
size = len(target)
# Create a object of disjoint set
dis_obj = disjoint_set()
for (u, v) in pairs:
ascii_1 = ord(u) - ord('a')
ascii_2 = ord(v) - ord('a')
# Take union of both the characters
dis_obj.union(ascii_1, ascii_2)
left = 0
right = size-1
# Check for palindrome condition
# For every character
while(left < right):
s1 = target[left]
s2 = target[right]
# If characters not same
if (s1 != s2):
# Convert to ascii value between 0-25
ascii_1 = ord(s1) - ord('a')
ascii_2 = ord(s2) - ord('a')
# Check if both the words
# Belong to same set
if (not dis_obj.connected(ascii_1, ascii_2)):
return False
left += 1
right -= 1
# Finally return True
return (True)
if __name__ == '__main__':
target = "geeks"
pairs = [["g", "s"], ["e", "k"]]
obj = Solution()
ans = obj.solve(target, pairs)
if (ans):
print('true')
else:
print('false')
Javascript
<script>
// JavaScript code for the above approach:
class disjoint_set{
constructor(){
// string consist of only smallcase letters
this.parent = new Array(26)
for(let i=0;i<26;i++){
this.parent[i] = i
}
this.rank = new Array(26).fill(1)
}
find_parent(x){
if (this.parent[x] == x)
return x
this.parent[x] = this.find_parent(this.parent[x])
return (this.parent[x])
}
union(u, v){
let p1 = this.find_parent(u)
let p2 = this.find_parent(v)
if (p1 != p2){
// rank of p1 smaller than p2
if(this.rank[p1] < this.rank[p2])
this.parent[p1] = p2
else if(this.rank[p2] < this.rank[p1])
this.parent[p2] = p1
// rank of p2 equal to p1
else{
this.parent[p2] = p1
this.rank[p1] += 1
}
}
}
connected(w1, w2){
let p1 = this.find_parent(w1)
let p2 = this.find_parent(w2)
if (p1 == p2)
return true
return false
}
}
class Solution{
solve(target, pairs){
let size = target.length
// Create a object of disjoint set
let dis_obj = new disjoint_set()
for (let [u, v] of pairs){
let ascii_1 = (u).charCodeAt(0) - ('a').charCodeAt(0)
let ascii_2 = (v).charCodeAt(0) - ('a').charCodeAt(0)
// Take union of both the characters
dis_obj.union(ascii_1, ascii_2)
}
let left = 0
let right = size-1
// Check for palindrome condition
// For every character
while(left < right){
let s1 = target[left]
let s2 = target[right]
// If characters not same
if (s1 != s2){
// Convert to ascii value between 0-25
let ascii_1 = s1.charCodeAt(0) - 'a'.charCodeAt(0)
let ascii_2 = s2.charCodeAt(0) - 'a'.charCodeAt(0)
// Check if both the words
// Belong to same set
if (!dis_obj.connected(ascii_1, ascii_2))
return false
}
left += 1
right -= 1
}
// Finally return true
return true
}
}
// driver code
let target = "geeks"
let pairs = [["g", "s"], ["e", "k"]]
let obj = new Solution()
let ans = obj.solve(target, pairs)
if (ans)
document.write('true')
else
document.write('false')
// This code is contributed by shinjanpatra
</script>
true
Complejidad temporal: O(N)
Espacio auxiliar: O(1)