Dada una string S y un carácter X donde ![X \ varepsilon S [i]](https://www.geeksforgeeks.org/wp-content/ql-cache/quicklatex.com-6284f6c649164ddea57d8294e95483d6_l3.png "Procesado por QuickLaTeX.com")
, para algunos 
. La tarea es devolver una array de distancias que representan la distancia más corta desde el carácter X hasta cualquier otro carácter de la string.
Ejemplos:
Entrada: S = «geeksforgeeks», X = ‘e’
Salida: [1, 0, 0, 1, 2, 3, 3, 2, 1, 0, 0, 1, 2]
para S[0] = ‘g ‘ el ‘e’ más cercano está a una distancia = 1, es decir, S[1] = ‘e’.
de manera similar, para S[1] = ‘e’, distancia = 0.
para S[6] = ‘o’, distancia = 3 ya que tenemos S[9] = ‘e’, y así sucesivamente.
Entrada: S = «holamundo», X = ‘o’
Salida: [4, 3, 2, 1, 0, 1, 0, 1, 2, 3]
Enfoque 1: para cada carácter en el índice i en S[] , intentemos encontrar la distancia al siguiente carácter X de izquierda a derecha y de derecha a izquierda. La respuesta será el mínimo de estos dos valores.
- Al ir de izquierda a derecha, recordamos el índice del último carácter X que hemos visto. Entonces la respuesta es i – anterior .
- Al ir de derecha a izquierda, la respuesta es anterior – i .
- Tomamos el mínimo de estas dos respuestas para crear nuestra array de distancia final.
- Finalmente, imprima la array.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of above approach
#include <bits/stdc++.h>
using namespace std;
// Function to return required
// array of distances
void shortestDistance(string S, char X)
{
// Find distance from occurrences of X
// appearing before current character.
int prev = INT_MAX;
vector<int> ans;
for (int i = 0; i < S.length(); i++)
{
if (S[i] == X)
prev = i;
if (prev == INT_MAX)
ans.push_back(INT_MAX);
else
ans.push_back(i - prev);
}
// Find distance from occurrences of X
// appearing after current character and
// compare this distance with earlier.
prev = INT_MAX;
for (int i = S.length() - 1; i >= 0; i--)
{
if (S[i] == X)
prev = i;
if (prev != INT_MAX)
ans[i] = min(ans[i], prev - i);
}
for (auto val: ans)
cout << val << ' ';
}
// Driver code
int main()
{
string S = "helloworld";
char X = 'o';
shortestDistance(S, X);
return 0;
}
// This code is contributed by Rituraj Jain
Java
// Java implementation of above approach
import java.util.*;
class GFG
{
// Function to return required
// array of distances
static void shortestDistance(String S, char X)
{
// Find distance from occurrences of X
// appearing before current character.
int prev = Integer.MAX_VALUE;
Vector<Integer> ans = new Vector<>();
for (int i = 0; i < S.length(); i++)
{
if (S.charAt(i) == X)
prev = i;
if (prev == Integer.MAX_VALUE)
ans.add(Integer.MAX_VALUE);
else
ans.add(i - prev);
}
// Find distance from occurrences of X
// appearing after current character and
// compare this distance with earlier.
prev = Integer.MAX_VALUE;
for (int i = S.length() - 1; i >= 0; i--)
{
if (S.charAt(i) == X)
prev = i;
if (prev != Integer.MAX_VALUE)
ans.set(i, Math.min(ans.get(i), prev - i));
}
for (Integer val: ans)
System.out.print(val+" ");
}
// Driver code
public static void main(String[] args)
{
String S = "geeksforgeeks";
char X = 'g';
shortestDistance(S, X);
}
}
// This code is contributed by Rajput-Ji
Python3
# Python3 implementation of above approach
# Function to return required
# array of distances
def shortestDistance(S, X):
# Find distance from occurrences of X
# appearing before current character.
inf = float('inf')
prev = inf
ans = []
for i,j in enumerate(S):
if S[i] == X:
prev = i
if (prev == inf) :
ans.append(inf)
else :
ans.append(i - prev)
# Find distance from occurrences of X
# appearing after current character and
# compare this distance with earlier.
prev = inf
for i in range(len(S) - 1, -1, -1):
if S[i] == X:
prev = i
if (X != inf):
ans[i] = min(ans[i], prev - i)
# return array of distance
return ans
# Driver code
S = "geeksforgeeks"
X = "g"
# Function call to print answer
print(shortestDistance(S, X))
C#
// C# implementation of above approach
using System;
using System.Collections.Generic;
class GFG
{
// Function to return required
// array of distances
public static void shortestDistance(String S, char X){
// Find distance from occurrences of X
// appearing before current character.
int prev = int.MaxValue;
List<int> ans = new List<int>();
for (int i=0; i<S.Length; i++)
{
if (S[i] == X)
prev = i;
if (prev == int.MaxValue)
ans.Add(int.MaxValue);
else
ans.Add(i-prev);
}
// Find distance from occurrences of X
// appearing after current character and
// compare this distance with earlier.
prev = int.MaxValue;
for (int i=S.Length-1; i>=0; i--)
{
if (S[i] == X)
prev = i;
if (prev != int.MaxValue)
ans[i] = Math.Min(ans[i], prev-i);
}
foreach (var i in ans)
Console.Write(i + " ");
}
// Driver code
public static void Main(String[] args)
{
String S = "geeksforgeeks";
char X = 'g';
shortestDistance(S, X);
}
}
// This code is contributed by
// sanjeev2552
Javascript
<script>
// JavaScript implementation of above approach
// Function to return required
// array of distances
function shortestDistance(S, X)
{
// Find distance from occurrences of X
// appearing before current character.
let prev = Number.MAX_VALUE;
let ans = [];
for (let i = 0; i < S.length; i++)
{
if (S[i] == X)
prev = i;
if (prev == Number.MAX_VALUE)
ans.push(Number.MAX_VALUE);
else
ans.push(i - prev);
}
// Find distance from occurrences of X
// appearing after current character and
// compare this distance with earlier.
prev = Number.MAX_VALUE;
for (let i = S.length - 1; i >= 0; i--)
{
if (S[i] == X)
prev = i;
if (prev != Number.MAX_VALUE)
ans[i] = Math.min(ans[i], prev - i);
}
for (let val of ans)
document.write(val + ' ');
}
// Driver code
let S = "helloworld";
let X = 'o';
shortestDistance(S, X);
// This code is contributed by Shinjanpatra
</script>
Producción
4 3 2 1 0 1 0 1 2 3
Complejidad de tiempo: O(|S|), Espacio auxiliar: O(1)
Enfoque 2: cree una lista que contenga la ocurrencia del carácter y luego cree dos punteros que apunten a dos ubicaciones inmediatas en esta lista, ahora itere sobre la string para encontrar la diferencia entre estos dos punteros e inserte el mínimo en la lista de resultados. Si el puntero 2 está más cerca del carácter actual, mueva los punteros un paso adelante.
- Cree una lista que contenga posiciones del carácter requerido en la string y una lista vacía para contener la array de resultados.
- Cree dos punteros a la lista p1=0 y p2=0 si la longitud de la lista es 1 sino p2=1
- Repita la string y compare los valores en estos punteros (v1=p1->value & v2=p2->value) con el índice actual (i) .
- Si i <= v1, presione v1-i en la lista de resultados.
- De lo contrario, si i <= v2
- si estoy más cerca de v1, presione i-v1 en la lista de resultados
- De lo contrario, presione v2-i en la lista de resultados y mueva el puntero un paso hacia adelante si es posible
- De lo contrario, empuje i-v1 a la lista de resultados
- Devolver lista de resultados
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of above approach
#include <bits/stdc++.h>
using namespace std;
// Function to return required
// vector of distances
vector<int> shortestToChar(string s, char c)
{
// list to hold position of c in s
vector<int> list;
// list to hold the result
vector<int> res;
// length of string
int len = s.length();
// Iterate over string to create list
for (int i = 0; i < len; i++) {
if (s[i] == c) {
list.push_back(i);
}
}
int p1, p2, v1, v2;
// max value of p2
int l = list.size() - 1;
// Initialize the pointers
p1 = 0;
p2 = l > 0 ? 1 : 0;
// Create result array
for (int i = 0; i < len; i++) {
// Values at current pointers
v1 = list[p1];
v2 = list[p2];
// Current Index is before than p1
if (i <= v1) {
res.push_back(v1 - i);
}
// Current Index is between p1 and p2
else if (i <= v2) {
// Current Index is nearer to p1
if (i - v1 < v2 - i) {
res.push_back(i - v1);
}
// Current Index is nearer to p2
else {
res.push_back(v2 - i);
// Move pointer 1 step ahead
p1 = p2;
p2 = p2 < l ? (p2 + 1) : p2;
}
}
// Current index is after p2
else {
res.push_back(i - v2);
}
}
return res;
}
// Driver code
int main()
{
string s = "geeksforgeeks";
char c = 'e';
vector<int> res = shortestToChar(s, c);
for (auto i : res)
cout << i << " ";
return 0;
}
// This code is contributed by Shivam Sharma
C
// C implementation of above approach
#include <stdio.h>
#define MAX_SIZE 100
// Function to return required
// vector of distances
void shortestToChar(char s[], char c, int* res)
{
// list to hold position of c in s
int list[MAX_SIZE];
// length of string
int len = 0;
// To hold size of list
int l = 0;
// Iterate over string to create list
while (s[len] != '\0') {
if (s[len] == c) {
list[l] = len;
l++;
}
len++;
}
int p1, p2, v1, v2;
// max value of p2
l = l - 1;
// Initialize the pointers
p1 = 0;
p2 = l > 0 ? 1 : 0;
// Create result array
for (int i = 0; i < len; i++) {
// Values at current pointers
v1 = list[p1];
v2 = list[p2];
// Current Index is before than p1
if (i <= v1) {
res[i] = (v1 - i);
}
// Current Index is between p1 and p2
else if (i <= v2) {
// Current Index is nearer to p1
if (i - v1 < v2 - i) {
res[i] = (i - v1);
}
// Current Index is nearer to p2
else {
res[i] = (v2 - i);
// Move pointer 1 step ahead
p1 = p2;
p2 = p2 < l ? (p2 + 1) : p2;
}
}
// Current index is after p2
else {
res[i] = (i - v2);
}
}
}
// Driver code
int main()
{
char s[] = "geeksforgeeks";
char c = 'e';
int res[MAX_SIZE];
shortestToChar(s, c, res);
int i = 0;
while (s[i] != '\0')
printf("%d ", res[i++]);
return 0;
}
// This code is contributed by Shivam Sharma
Python3
# Python implementation of above approach # Function to return required # vector of distances def shortestToChar(s,c): # list to hold position of c in s list = [] # list to hold the result res = [] # length of string Len = len(s) # Iterate over string to create list for i in range(Len): if (s[i] == c): list.append(i) # max value of p2 l = len(list) - 1 # Initialize the pointers p1 = 0 p2 = 1 if l > 0 else 0 # Create result array for i in range(Len): # Values at current pointers v1 = list[p1] v2 = list[p2] # Current Index is before than p1 if (i <= v1): res.append(v1 - i) # Current Index is between p1 and p2 elif (i <= v2): # Current Index is nearer to p1 if (i - v1 < v2 - i): res.append(i - v1) # Current Index is nearer to p2 else: res.append(v2 - i) # Move pointer 1 step ahead p1 = p2 p2 = (p2 + 1) if (p2<l) else p2 # Current index is after p2 else: res.append(i - v2) return res # Driver code s = "geeksforgeeks" c = 'e' res = shortestToChar(s, c) for i in res: print(i,end = " ") # This code is contributed by shinjanpatra
Javascript
<script>
// JavaScript implementation of above approach
// Function to return required
// vector of distances
function shortestToChar(s,c)
{
// list to hold position of c in s
let list = [];
// list to hold the result
let res = [];
// length of string
let len = s.length;
// Iterate over string to create list
for (let i = 0; i < len; i++) {
if (s[i] == c) {
list.push(i);
}
}
let p1, p2, v1, v2;
// max value of p2
let l = list.length - 1;
// Initialize the pointers
p1 = 0;
p2 = l > 0 ? 1 : 0;
// Create result array
for (let i = 0; i < len; i++) {
// Values at current pointers
v1 = list[p1];
v2 = list[p2];
// Current Index is before than p1
if (i <= v1) {
res.push(v1 - i);
}
// Current Index is between p1 and p2
else if (i <= v2) {
// Current Index is nearer to p1
if (i - v1 < v2 - i) {
res.push(i - v1);
}
// Current Index is nearer to p2
else {
res.push(v2 - i);
// Move pointer 1 step ahead
p1 = p2;
p2 = p2 < l ? (p2 + 1) : p2;
}
}
// Current index is after p2
else {
res.push(i - v2);
}
}
return res;
}
// Driver code
let s = "geeksforgeeks";
let c = 'e';
let res = shortestToChar(s, c);
for (let i of res)
document.write(i , end = " ");
// This code is contributed by Shinjanpatra
</script>
Producción
1 0 0 1 2 3 3 2 1 0 0 1 2
Complejidad de tiempo: O(n), Complejidad de espacio: O(n)
Publicación traducida automáticamente
Artículo escrito por Sanjit_Prasad y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA