Dada una string S y una array de palabras de igual longitud (strings) arr[]. La tarea es encontrar el índice de inicio mínimo de la substring que contiene todas las palabras dadas de manera contigua . Si no se encuentra dicho índice, devuelve -1 .
Nota: Las palabras pueden estar en cualquier secuencia.
Ejemplos:
Entrada : arr[ ] = {“bat”, “bal”, “cat”}, S = “hellocatbyebalbatcatyo”
Salida : 11
Explicación : la substring que comienza en el índice 11 contiene las 3 palabras de manera contigua.Entrada : arr[ ] = {“hat”, “mat”}, S = “aslkfndsuvbsdlvnsk”
Salida : -1
Explicación : No hay ninguna substring que contenga ambas palabras de manera contigua.
Enfoque: la tarea se puede resolver encontrando cualquiera de las palabras en el índice mínimo y luego simulando el proceso desde el índice final de la primera palabra para verificar si todas las demás palabras están presentes en posiciones contiguas o no.
Siga los pasos para resolver el problema:
- Guarde todas las palabras en un conjunto desordenado, digamos st, para buscar las palabras en tiempo constante.
- Recorra la string y verifique la substring comenzando en cada índice de longitud M (longitud de cada palabra), una vez que se encuentra una substring válida, que está presente en S, comience a simular el proceso después del índice final de la substring anterior y verifique si todas las demás palabras están presentes de manera contigua o no.
- Si todas las palabras se encuentran de forma contigua, devuelve el índice mínimo donde se encuentra, de lo contrario, devuelve -1.
A continuación se muestra la implementación del enfoque anterior:
C++14
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the min index
int minIndex(string arr[], string S, int N, int M)
{
// Unordered set to store all words
unordered_set<string> st;
// Insert each word in the set
for (int i = 0; i < N; i++)
st.insert(arr[i]);
// Traverse over the string s
for (int i = 0; i < S.size() - M; i++) {
// Substring to check whether
// it is part of array of
// words or not
string x = S.substr(i, M);
// Variables to check the condition, store the
// index and keep count of words
int p = 0, k = -1, d = N;
// If substring is one of the words
if (st.find(x) != st.end()) {
// Store the index
k = i;
// Decrement d
d--;
// Check further
for (int j = i + M; j < S.size() - M; j += M) {
// Substring to check
// whether it is part of
// array of words or not
string y = S.substr(j, M);
// If substring is not part of word
if (d == 0)
break;
if (st.find(y) == st.end()) {
p = 1;
i = j - 1;
break;
}
d--;
}
}
// If index is found, return the index
if (p == 0 and k != -1)
return k;
}
// If no index found, return -1
return -1;
}
// Driver Code
int main()
{
// Input
string arr[] = { "bat", "bal", "cat" };
string S = "hellocatbyebalbatcatyo";
int N = sizeof(arr) / sizeof(arr[0]);
int M = arr[0].size();
// Function call to find the minimum index
cout << minIndex(arr, S, N, M);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Function to find the min index
static int minIndex(String arr[], String S, int N, int M)
{
// Unordered set to store all words
HashSet<String> st = new HashSet<String>();
// Insert each word in the set
for (int i = 0; i < N; i++)
st.add(arr[i]);
// Traverse over the String s
for (int i = 0; i < S.length() - M; i++)
{
// SubString to check whether
// it is part of array of
// words or not
String x = S.substring(i, i+M);
// Variables to check the condition, store the
// index and keep count of words
int p = 0, k = -1, d = N;
// If subString is one of the words
if (st.contains(x)) {
// Store the index
k = i;
// Decrement d
d--;
// Check further
for (int j = i + M; j < S.length() - M; j += M) {
// SubString to check
// whether it is part of
// array of words or not
String y = S.substring(j, j+M);
// If subString is not part of word
if (d == 0)
break;
if (!st.contains(y)) {
p = 1;
i = j - 1;
break;
}
d--;
}
}
// If index is found, return the index
if (p == 0 && k != -1)
return k;
}
// If no index found, return -1
return -1;
}
// Driver Code
public static void main(String[] args)
{
// Input
String arr[] = { "bat", "bal", "cat" };
String S = "hellocatbyebalbatcatyo";
int N = arr.length;
int M = arr[0].length();
// Function call to find the minimum index
System.out.print(minIndex(arr, S, N, M));
}
}
// This code is contributed by 29AjayKumar
Python3
# Python program for the above approach # Function to find the min index def minIndex(arr, S, N, M): # Unordered set to store all words st = set(arr) # Insert each word in the set for i in range(len(S)-M): x = S[i: i+M] # Variables to check the condition, store the # index and keep count of words p = 0 k = -1 d = N # If substring is one of the words if x in st: # Store the index k = i # Decrement d d -= 1 # Traverse over the string s for j in range(i+M, len(S)-M, M): # Substring to check # whether it is part of # array of words or not y = S[j: j+M] # If substring is not part of word if d == 0: break if y not in st: p = 1 i = j-1 break d -= 1 # If index is found, return the index if p == 0 and k != -1: return k # If no index found return -1 return -1 # Driver code arr = ["bat", "bal", "cat"] S = "hellocatbyebalbatcatyo" N = len(arr) M = len(arr[0]) print(minIndex(arr, S, N, M)) # This code is contributed by parthmanchanda81
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG{
// Function to find the min index
static int minIndex(string []arr, string S, int N, int M)
{
// Unordered set to store all words
HashSet<string> st = new HashSet<string>();
// Insert each word in the set
for (int i = 0; i < N; i++)
st.Add(arr[i]);
// Traverse over the string s
for (int i = 0; i < S.Length - M; i++) {
// Substring to check whether
// it is part of array of
// words or not
string x = S.Substring(i, M);
// Variables to check the condition, store the
// index and keep count of words
int p = 0, k = -1, d = N;
// If substring is one of the words
if (st.Contains(x)) {
// Store the index
k = i;
// Decrement d
d--;
// Check further
for (int j = i + M; j < S.Length - M; j += M) {
// Substring to check
// whether it is part of
// array of words or not
string y = S.Substring(j, M);
// If substring is not part of word
if (d == 0)
break;
if (st.Contains(y)==false) {
p = 1;
i = j - 1;
break;
}
d--;
}
}
// If index is found, return the index
if (p == 0 && k != -1)
return k;
}
// If no index found, return -1
return -1;
}
// Driver Code
public static void Main()
{
// Input
string []arr = { "bat", "bal", "cat" };
string S = "hellocatbyebalbatcatyo";
int N = arr.Length;
int M = arr[0].Length;
// Function call to find the minimum index
Console.Write(minIndex(arr, S, N, M));
}
}
// This code is contributed by SURENDRA_GANGWAR.
Javascript
<script>
// Javascript program for the above approach
// Function to find the min index
function minIndex(arr, S, N, M) {
// Unordered set to store all words
let st = new Set();
// Insert each word in the set
for (let i = 0; i < N; i++) st.add(arr[i]);
// Traverse over the string s
for (let i = 0; i < S.length - M; i++) {
// Substring to check whether
// it is part of array of
// words or not
let x = S.substr(i, M);
console.log(x);
// Variables to check the condition, store the
// index and keep count of words
let p = 0,
k = -1,
d = N;
// If substring is one of the words
if (st.has(x)) {
// Store the index
k = i;
// Decrement d
d--;
// Check further
for (let j = i + M; j < S.length - M; j += M) {
// Substring to check
// whether it is part of
// array of words or not
let y = S.substr(j, M);
// If substring is not part of word
if (d == 0) break;
if (!st.has(y)) {
p = 1;
i = j - 1;
break;
}
d--;
}
}
// If index is found, return the index
if (p == 0 && k != -1) return k;
}
// If no index found, return -1
return -1;
}
// Driver Code
// Input
let arr = ["bat", "bal", "cat"];
let S = "hellocatbyebalbatcatyo";
let N = arr.length;
let M = arr[0].length;
// Function call to find the minimum index
document.write(minIndex(arr, S, N, M));
// This code is contributed by _saurabh_jaiswal.
</script>
Producción:
11
Complejidad de tiempo : O(S*M), S es la longitud de la string y M es la longitud de cada palabra
Espacio auxiliar : O(N), N es el número de palabras