Dadas dos strings s1 y s2 con alfabetos en minúsculas que tienen una longitud N . Las strings s1 y s2 inicialmente pueden contener algunos espacios en blanco, la tarea es encontrar operaciones mínimas para convertir una string s1 a s2.
- Inicialmente, si hay espacios en blanco, deben ser reemplazados por cualquier mismo carácter que cueste 0 y
- Cualquier vocal en la string puede ser reemplazada por cualquier consonante y cualquier consonante puede ser reemplazada por cualquier vocal que cueste 1.
Ejemplos:
Entrada: s1 = “g_e_s”, s2 = “ge_ks”
Salida: 1
Explicación: Reemplazando los espacios en blanco con ‘e’, las strings se convierten en s1= “geees”, s2 = “geeks”
En el tercer índice de s1 convertir e -> k que cuesta solo 1 operación.Entrada: s1 = “abcd”, s2 = “aeca”
Salida: 2
Enfoque: dado que solo hay 26 caracteres en minúsculas, si hay espacios en blanco en las strings, los espacios en blanco se pueden reemplazar por cada uno de estos caracteres y se puede calcular el costo mínimo para convertir la string s1 a s2. Si ambos caracteres de la string, uno es vocal y el otro es consonante o viceversa, solo cuesta una unidad transformar un carácter. Si ambos caracteres son vocales o consonantes y no son iguales entonces tiene un costo de 2; consonante -> vocal -> consonante (costo = 2) o vocal -> consonante -> vocal (costo = 2).
Siga estos pasos para resolver el problema anterior:
- Si las dos longitudes de las strings no son iguales, devuelve -1 .
- Inicialice n con la longitud y res como INT_MAX .
- Ahora itere a través de cada uno de los 26 caracteres.
- Inicialice la variable ops = 0 para almacenar los costos requeridos.
- Recorra desde el rango [0, n) y verifique si hay un espacio en blanco en alguna de las strings.
- Si hay un espacio en blanco, inicialice los caracteres c1 y c2 para almacenar los caracteres modificados.
- Si ambos caracteres c1 == c2 (el carácter después de reemplazar el espacio en blanco) no se requieren operaciones.
- De lo contrario, si ambas son vocales o consonantes, requiere 2 operaciones; de lo contrario, solo requiere 1 operación, agréguela a la variable ops.
- Después del recorrido, almacene las operaciones mínimas en el res (min(ops, res)) .
- Imprime el resultado res .
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 whether
// a character is vowel or not
bool isVowel(char c)
{
return (c == 'a' || c == 'e' || c == 'i'
|| c == 'o' || c == 'u');
}
// Function to calculate minimum cost
void minCost(string s1, string s2)
{
// If both the lengths are not equal
if (s1.length() != s2.length()) {
cout << -1 << endl;
return;
}
int n = s1.length();
// Initialize res with max value
int res = INT_MAX;
// Iterate through every character
// and check the minimum cost by
// replacing the blank by all letters
for (char c = 'a'; c <= 'z'; c++) {
// Initialize ops to check
// the cost required by replacing
// each char c
int ops = 0;
for (int i = 0; i < n; i++) {
// If it is blank replace with c
char c1 = s1[i] == '_' ? c : s1[i];
char c2 = s2[i] == '_' ? c : s2[i];
// If both are equal no ops required
if (c1 == c2)
continue;
else {
// If both are vowels or consonants
// it requires cost as two
// vowel->consonant ->vowel
// and vice versa
// Else 1 operation
ops
= ops
+ (isVowel(s1[i]) != isVowel(s2[i])
? 2
: 1);
}
}
// Take the minimum
if (ops < res) {
res = ops;
}
}
// Print the result
cout << res << endl;
}
// Driver code
int main()
{
// Initialize the strings
string s1 = "g_e_s", s2 = "ge_ks";
// Function call
minCost(s1, s2);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
public class GFG
{
// Function to check whether
// a character is vowel or not
static boolean isVowel(char c)
{
return (c == 'a' || c == 'e' || c == 'i'
|| c == 'o' || c == 'u');
}
// Function to calculate minimum cost
static void minCost(String s1, String s2)
{
// If both the lengths are not equal
if (s1.length() != s2.length()) {
System.out.println(-1);
return;
}
int n = s1.length();
// Initialize res with max value
int res = Integer.MAX_VALUE;
// Iterate through every character
// and check the minimum cost by
// replacing the blank by all letters
for (char c = 'a'; c <= 'z'; c++) {
// Initialize ops to check
// the cost required by replacing
// each char c
int ops = 0;
for (int i = 0; i < n; i++) {
// If it is blank replace with c
char c1 = s1.charAt(i) == '_' ? c : s1.charAt(i);
char c2 = s2.charAt(i) == '_' ? c : s2.charAt(i);
// If both are equal no ops required
if (c1 == c2)
continue;
else {
// If both are vowels or consonants
// it requires cost as two
// vowel->consonant ->vowel
// and vice versa
// Else 1 operation
ops
= ops
+ (isVowel(s1.charAt(i)) != isVowel(s2.charAt(i))
? 2
: 1);
}
}
// Take the minimum
if (ops < res) {
res = ops;
}
}
// Print the result
System.out.println(res);
}
// Driver code
public static void main(String args[])
{
// Initialize the strings
String s1 = "g_e_s", s2 = "ge_ks";
// Function call
minCost(s1, s2);
}
}
// This code is contributed by Samim Hossain Mondal.
Python3
# Python 3 program for the above approach
import sys
# Function to check whether
# a character is vowel or not
def isVowel(c):
return (c == 'a' or c == 'e' or c == 'i'
or c == 'o' or c == 'u')
# Function to calculate minimum cost
def minCost(s1, s2):
# If both the lengths are not equal
if (len(s1) != len(s2)):
print(-1)
return
n = len(s1)
# Initialize res with max value
res = sys.maxsize
# Iterate through every character
# and check the minimum cost by
# replacing the blank by all letters
for c in range(ord('a'), ord('z')+1):
# Initialize ops to check
# the cost required by replacing
# each char c
ops = 0
for i in range(n):
# If it is blank replace with c
if s1[i] == '_':
c1 = chr(c)
else:
c1 = s1[i]
if s2[i] == '_':
c2 = chr(c)
else:
c2 = s2[i]
# If both are equal no ops required
if (c1 == c2):
continue
else:
# If both are vowels or consonants
# it requires cost as two
# vowel->consonant ->vowel
# and vice versa
# Else 1 operation
if isVowel(s1[i]) != isVowel(s2[i]):
ops += 2
else:
ops += 1
# Take the minimum
if (ops < res):
res = ops
# Print the result
print(res)
# Driver code
if __name__ == "__main__":
# Initialize the strings
s1 = "g_e_s"
s2 = "ge_ks"
# Function call
minCost(s1, s2)
# This code is contributed by ukasp.
C#
// C# program for the above approach
using System;
class GFG
{
// Function to check whether
// a character is vowel or not
static bool isVowel(char c)
{
return (c == 'a' || c == 'e' || c == 'i'
|| c == 'o' || c == 'u');
}
// Function to calculate minimum cost
static void minCost(string s1, string s2)
{
// If both the lengths are not equal
if (s1.Length != s2.Length) {
Console.WriteLine(-1);
return;
}
int n = s1.Length;
// Initialize res with max value
int res = Int32.MaxValue;
// Iterate through every character
// and check the minimum cost by
// replacing the blank by all letters
for (char c = 'a'; c <= 'z'; c++) {
// Initialize ops to check
// the cost required by replacing
// each char c
int ops = 0;
for (int i = 0; i < n; i++) {
// If it is blank replace with c
char c1 = s1[i] == '_' ? c : s1[i];
char c2 = s2[i] == '_' ? c : s2[i];
// If both are equal no ops required
if (c1 == c2)
continue;
else {
// If both are vowels or consonants
// it requires cost as two
// vowel->consonant ->vowel
// and vice versa
// Else 1 operation
ops
= ops
+ (isVowel(s1[i]) != isVowel(s2[i])
? 2
: 1);
}
}
// Take the minimum
if (ops < res) {
res = ops;
}
}
// Print the result
Console.WriteLine(res);
}
// Driver code
public static void Main()
{
// Initialize the strings
string s1 = "g_e_s", s2 = "ge_ks";
// Function call
minCost(s1, s2);
}
}
// This code is contributed by Samim Hossain Mondal.
Javascript
<script>
// Javascript program for the above approach
// Function to check whether
// a character is vowel or not
function isVowel(c)
{
return (c == 'a' || c == 'e' || c == 'i'
|| c == 'o' || c == 'u');
}
// Function to calculate minimum cost
function minCost(s1, s2)
{
// If both the lengths are not equal
if (s1.length != s2.length) {
document.write(-1);
return;
}
let n = s1.length;
// Initialize res with max value
let res = Number. MAX_SAFE_INTEGER;
// Iterate through every character
// and check the minimum cost by
// replacing the blank by all letters
let c = 'a';
for (let j = 0; j < 26; j++) {
// Initialize ops to check
// the cost required by replacing
// each char c
let ops = 0;
for (let i = 0; i < n; i++) {
// If it is blank replace with c
let c1 = s1[i] == '_' ? c : s1[i];
let c2 = s2[i] == '_' ? c : s2[i];
// If both are equal no ops required
if (c1 == c2)
continue;
else {
// If both are vowels or consonants
// it requires cost as two
// vowel->consonant ->vowel
// and vice versa
// Else 1 operation
ops
= ops
+ (isVowel(s1[i]) != isVowel(s2[i])
? 2
: 1);
}
}
c = String.fromCharCode(c.charCodeAt(0) + 1);
// Take the minimum
if (ops < res) {
res = ops;
}
}
// Print the result
document.write(res);
}
// Driver code
// Initialize the strings
let s1 = "g_e_s";
let s2 = "ge_ks";
// Function call
minCost(s1, s2);
// This code is contributed by Samim Hossain Mondal.
</script>
Producción
1
Complejidad de tiempo: O(26* N)
Complejidad de espacio: O(1)
Publicación traducida automáticamente
Artículo escrito por lokeshpotta20 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA