Dada una string S de longitud N que consta de caracteres en minúsculas, la tarea es encontrar el costo mínimo para pasar del índice i al índice j .
En cualquier índice k , el costo de saltar al índice k+1 y k-1 (sin salirse de los límites) es 1.
Además, el costo de saltar a cualquier índice m tal que S[m] = S[k] es 0
Ejemplos:
Entrada: S = “abcde”, i = 0, j = 4
Salida: 4
Explicación:
El camino más corto será:
0->1->2->3->4
Por lo tanto, la respuesta será 4.Entrada: S = “abcdefb”, i = 0, j = 5
Salida: 2
Explicación:
0->1->6->5
0->1 el peso del borde es 1, 1->6 el peso del borde es 0 y 6 ->5 el peso del borde es 1.
Por lo tanto, la respuesta será 2
Acercarse:
- Un enfoque para resolver este problema es 0-1 BFS .
- La configuración se puede visualizar como un gráfico con N Nodes.
- Todos los Nodes estarán conectados a Nodes adyacentes con una arista de peso ‘1’ y Nodes con los mismos caracteres con una arista de peso ‘0’.
- En esta configuración, se puede ejecutar 0-1 BFS para encontrar la ruta más corta desde el índice ‘i’ hasta el índice ‘j’.
Complejidad temporal: O(N^2) – Como el número de vértices sería de O(N^2)
Enfoque eficiente:
- Para cada carácter X , se encuentran todos los caracteres para los que es adyacente.
- Se crea un gráfico con el número de Nodes como el número de caracteres distintos en la string, cada uno de los cuales representa un carácter.
- Cada Node X tendrá un borde de peso 1 con todos los Nodes representando caracteres adyacentes al carácter X.
- Entonces BFS se puede ejecutar desde los Nodes que representan S[i] a los Nodes que representan S[j] en este nuevo gráfico
Complejidad del tiempo: O(N)
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the above approach.
#include <bits/stdc++.h>
using namespace std;
// function to find the minimum cost
int findMinCost(string s, int i, int j)
{
// graph
vector<vector<int> > gr(26);
// adjacency matrix
bool edge[26][26];
// initialising adjacency matrix
for (int k = 0; k < 26; k++)
for (int l = 0; l < 26; l++)
edge[k][l] = 0;
// creating adjacency list
for (int k = 0; k < s.size(); k++) {
// pushing left adjacent element for index 'k'
if (k - 1 >= 0
and !edge[s[k] - 97][s[k - 1] - 97])
gr[s[k] - 97].push_back(s[k - 1] - 97),
edge[s[k] - 97][s[k - 1] - 97] = 1;
// pushing right adjacent element for index 'k'
if (k + 1 <= s.size() - 1
and !edge[s[k] - 97][s[k + 1] - 97])
gr[s[k] - 97].push_back(s[k + 1] - 97),
edge[s[k] - 97][s[k + 1] - 97] = 1;
}
// queue to perform BFS
queue<int> q;
q.push(s[i] - 97);
// visited array
bool v[26] = { 0 };
// variable to store depth of BFS
int d = 0;
// BFS
while (q.size()) {
// number of elements in the current level
int cnt = q.size();
// inner loop
while (cnt--) {
// current element
int curr = q.front();
// popping queue
q.pop();
// base case
if (v[curr])
continue;
v[curr] = 1;
// checking if the current node is required node
if (curr == s[j] - 97)
return d;
// iterating through the current node
for (auto it : gr[curr])
q.push(it);
}
// updating depth
d++;
}
return -1;
}
// Driver Code
int main()
{
// input variables
string s = "abcde";
int i = 0;
int j = 4;
// function to find the minimum cost
cout << findMinCost(s, i, j);
}
Java
// Java implementation of the above approach.
import java.util.*;
class GFG
{
// function to find the minimum cost
static int findMinCost(char[] s, int i, int j)
{
// graph
Vector<Integer>[] gr = new Vector[26];
for (int iN = 0; iN < 26; iN++)
gr[iN] = new Vector<Integer>();
// adjacency matrix
boolean[][] edge = new boolean[26][26];
// initialising adjacency matrix
for (int k = 0; k < 26; k++)
for (int l = 0; l < 26; l++)
edge[k][l] = false;
// creating adjacency list
for (int k = 0; k < s.length; k++)
{
// pushing left adjacent element for index 'k'
if (k - 1 >= 0 && !edge[s[k] - 97][s[k - 1] - 97])
{
gr[s[k] - 97].add(s[k - 1] - 97);
edge[s[k] - 97][s[k - 1] - 97] = true;
}
// pushing right adjacent element for index 'k'
if (k + 1 <= s.length - 1 && !edge[s[k] - 97][s[k + 1] - 97])
{
gr[s[k] - 97].add(s[k + 1] - 97);
edge[s[k] - 97][s[k + 1] - 97] = true;
}
}
// queue to perform BFS
Queue<Integer> q = new LinkedList<Integer>();
q.add(s[i] - 97);
// visited array
boolean[] v = new boolean[26];
// variable to store depth of BFS
int d = 0;
// BFS
while (q.size() > 0)
{
// number of elements in the current level
int cnt = q.size();
// inner loop
while (cnt-- > 0)
{
// current element
int curr = q.peek();
// popping queue
q.remove();
// base case
if (v[curr])
continue;
v[curr] = true;
// checking if the current node is required node
if (curr == s[j] - 97)
return d;
// iterating through the current node
for (Integer it : gr[curr])
q.add(it);
}
// updating depth
d++;
}
return -1;
}
// Driver Code
public static void main(String[] args)
{
// input variables
String s = "abcde";
int i = 0;
int j = 4;
// function to find the minimum cost
System.out.print(findMinCost(s.toCharArray(), i, j));
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 implementation of the above approach. from collections import deque as a queue # function to find minimum cost def findMinCost(s, i, j): # graph gr = [[] for i in range(26)] # adjacency matrix edge = [[ 0 for i in range(26)] for i in range(26)] # initialising adjacency matrix for k in range(26): for l in range(26): edge[k][l] = 0 # creating adjacency list for k in range(len(s)): # pushing left adjacent element for index 'k' if (k - 1 >= 0 and edge[ord(s[k]) - 97][ord(s[k - 1]) - 97] == 0): gr[ord(s[k]) - 97].append(ord(s[k - 1]) - 97) edge[ord(s[k]) - 97][ord(s[k - 1]) - 97] = 1 # pushing right adjacent element for index 'k' if (k + 1 <= len(s) - 1 and edge[ord(s[k]) - 97][ord(s[k + 1]) - 97] == 0): gr[ord(s[k]) - 97].append(ord(s[k + 1]) - 97) edge[ord(s[k]) - 97][ord(s[k + 1]) - 97] = 1 # queue to perform BFS q = queue() q.append(ord(s[i]) - 97) # visited array v = [0] * (26) # variable to store depth of BFS d = 0 # BFS while (len(q)): # number of elements in the current level cnt = len(q) # inner loop while (cnt > 0): # current element curr = q.popleft() # base case if (v[curr] == 1): continue v[curr] = 1 # checking if the current node is required node if (curr == ord(s[j]) - 97): return curr # iterating through the current node for it in gr[curr]: q.append(it) print() cnt -= 1 # updating depth d = d + 1 return -1 # Driver Code # input variables s = "abcde" i = 0 j = 4 # function to find the minimum cost print(findMinCost(s, i, j)) # This code is contributed by mohit kumar 29
C#
// C# implementation of the above approach.
using System;
using System.Collections.Generic;
class GFG
{
// function to find the minimum cost
static int findMinCost(char[] s, int i, int j)
{
// graph
List<int>[] gr = new List<int>[26];
for (int iN = 0; iN < 26; iN++)
gr[iN] = new List<int>();
// adjacency matrix
bool[,] edge = new bool[26, 26];
// initialising adjacency matrix
for (int k = 0; k < 26; k++)
for (int l = 0; l < 26; l++)
edge[k, l] = false;
// creating adjacency list
for (int k = 0; k < s.Length; k++)
{
// pushing left adjacent element for index 'k'
if (k - 1 >= 0 && !edge[s[k] - 97, s[k - 1] - 97])
{
gr[s[k] - 97].Add(s[k - 1] - 97);
edge[s[k] - 97, s[k - 1] - 97] = true;
}
// pushing right adjacent element for index 'k'
if (k + 1 <= s.Length - 1 &&
!edge[s[k] - 97, s[k + 1] - 97])
{
gr[s[k] - 97].Add(s[k + 1] - 97);
edge[s[k] - 97, s[k + 1] - 97] = true;
}
}
// queue to perform BFS
Queue<int> q = new Queue<int>();
q.Enqueue(s[i] - 97);
// visited array
bool[] v = new bool[26];
// variable to store depth of BFS
int d = 0;
// BFS
while (q.Count > 0)
{
// number of elements in the current level
int cnt = q.Count;
// inner loop
while (cnt-- > 0)
{
// current element
int curr = q.Peek();
// popping queue
q.Dequeue();
// base case
if (v[curr])
continue;
v[curr] = true;
// checking if the current node is required node
if (curr == s[j] - 97)
return d;
// iterating through the current node
foreach (int it in gr[curr])
q.Enqueue(it);
}
// updating depth
d++;
}
return -1;
}
// Driver Code
public static void Main(String[] args)
{
// input variables
String s = "abcde";
int i = 0;
int j = 4;
// function to find the minimum cost
Console.Write(findMinCost(s.ToCharArray(), i, j));
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Javascript implementation of the above approach.
// function to find the minimum cost
function findMinCost(s,i, j)
{
// graph
var gr = Array.from(Array(26), ()=> new Array());
// adjacency matrix
var edge = Array.from(Array(26), ()=> Array(26));
// initialising adjacency matrix
for (var k = 0; k < 26; k++)
for (var l = 0; l < 26; l++)
edge[k][l] = 0;
// creating adjacency list
for (var k = 0; k < s.length; k++) {
// pushing left adjacent element for index 'k'
if (k - 1 >= 0
&& !edge[s[k].charCodeAt(0) - 97][s[k - 1].charCodeAt(0) - 97])
gr[s[k].charCodeAt(0) - 97].push(s[k - 1].charCodeAt(0) - 97),
edge[s[k].charCodeAt(0) - 97][s[k - 1].charCodeAt(0) - 97] = 1;
// pushing right adjacent element for index 'k'
if (k + 1 <= s.length - 1
&& !edge[s[k].charCodeAt(0) - 97][s[k + 1].charCodeAt(0) - 97])
gr[s[k].charCodeAt(0) - 97].push(s[k + 1].charCodeAt(0) - 97),
edge[s[k].charCodeAt(0) - 97][s[k + 1].charCodeAt(0) - 97] = 1;
}
// queue to perform BFS
var q = [];
q.push(s[i].charCodeAt(0) - 97);
// visited array
var v = Array(26).fill(0);
// variable to store depth of BFS
var d = 0;
// BFS
while (q.length>0) {
// number of elements in the current level
var cnt = q.length;
// inner loop
while (cnt-->0) {
// current element
var curr = q[0];
// popping queue
q.shift();
// base case
if (v[curr])
continue;
v[curr] = 1;
// checking if the current node is required node
if (curr == s[j].charCodeAt(0) - 97)
return d;
// iterating through the current node
for(var it =0 ;it< gr[curr].length; it++)
{
q.push(gr[curr][it]);
}
}
// updating depth
d++;
}
return -1;
}
// Driver Code
// input variables
var s = "abcde";
var i = 0;
var j = 4;
// function to find the minimum cost
document.write( findMinCost(s, i, j));
</script>
Producción:
4
Publicación traducida automáticamente
Artículo escrito por DivyanshuShekhar1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA