Dada una array arr[] que consta de N strings y una string S de tamaño M , la tarea es encontrar la string lexicográficamente más pequeña que consta de la string S como prefijo. Si no existe ninguna string que comience con el prefijo S , imprima «-1» .
Ejemplos:
Entrada: arr[] = {“apple”, “appe”, “apl”, “aapl”, “appax”}, S = “app”
Salida: appax
Explicación:
El orden lexicográfico de las strings que consisten en “app” como la substring es {“aapl”, “apl”, “appax”, “appe”, “apple”}. La string lexicográfica más pequeña que contiene es “appax”.Entrada: arr[] = {“lata”, “hombre”, “va”}, S = “camioneta”
Salida: -1
Enfoque: El problema dado se puede resolver ordenando la array dada de strings arr[] de modo que todas las strings que comienzan con los prefijos S se presenten consecutivamente. Ahora recorra la array dada de strings arr[] y cuando la primera string cuyo prefijo coincida con S , imprima esa string y salga del bucle . De lo contrario, imprima «-1» .
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 find the whether the
// string temp starts with str or not
bool is_prefix(string temp, string str)
{
// Base Case
if (temp.length() < str.length())
return 0;
else {
// Check for the corresponding
// characters in temp & str
for (int i = 0;
i < str.length(); i++) {
if (str[i] != temp[i])
return 0;
}
return 1;
}
}
// Function to find lexicographic smallest
// string consisting of the string str
// as prefix
string lexicographicallyString(
string input[], int n, string str)
{
// Sort the given array string arr[]
sort(input, input + n);
for (int i = 0; i < n; i++) {
string temp = input[i];
// If the i-th string contains
// given string as a prefix,
// then print the result
if (is_prefix(temp, str)) {
return temp;
}
}
// If no string exists then
// return "-1"
return "-1";
}
// Driver Code
int main()
{
string arr[] = { "apple", "appe", "apl",
"aapl", "appax" };
string S = "app";
int N = 5;
cout << lexicographicallyString(
arr, N, S);
return 0;
}
Java
// Java program for the above approach
import java.util.Arrays;
class GFG {
// Function to find the whether the
// string temp starts with str or not
static boolean is_prefix(String temp, String str)
{
// Base Case
if (temp.length() < str.length())
return false;
else {
// Check for the corresponding
// characters in temp & str
for (int i = 0; i < str.length(); i++) {
if (str.charAt(i) != temp.charAt(i))
return false;
}
return true;
}
}
// Function to find lexicographic smallest
// string consisting of the string str
// as prefix
static String lexicographicallyString(String[] input,
int n, String str)
{
// Sort the given array string arr[]
Arrays.sort(input);
for (int i = 0; i < n; i++) {
String temp = input[i];
// If the i-th string contains
// given string as a prefix,
// then print the result
if (is_prefix(temp, str)) {
return temp;
}
}
// If no string exists then
// return "-1"
return "-1";
}
// Driver Code
public static void main(String args[])
{
String[] arr = { "apple", "appe", "apl", "aapl", "appax" };
String S = "app";
int N = 5;
System.out.println(
lexicographicallyString(arr, N, S));
}
}
// This code is contributed by AnkThon
Python3
# Python 3 program for the above approach # Function to find the whether the # string temp starts with str or not def is_prefix(temp, str): # Base Case if (len(temp) < len(str)): return 0 else: # Check for the corresponding # characters in temp & str for i in range(len(str)): if (str[i] != temp[i]): return 0 return 1 # Function to find lexicographic smallest # string consisting of the string str # as prefix def lexicographicallyString(input, n, str): # Sort the given array string arr[] input.sort() for i in range(n): temp = input[i] # If the i-th string contains # given string as a prefix, # then print the result if (is_prefix(temp, str)): return temp # If no string exists then # return "-1" return "-1" # Driver Code if __name__ == '__main__': arr = ["apple", "appe", "apl", "aapl", "appax"] S = "app" N = 5 print(lexicographicallyString(arr, N, S)) # This code is contributed by ipg2016107.
C#
// C# program for the above approach
using System;
class GFG {
// Function to find the whether the
// string temp starts with str or not
static bool is_prefix(string temp, string str)
{
// Base Case
if (temp.Length < str.Length)
return false;
else {
// Check for the corresponding
// characters in temp & str
for (int i = 0; i < str.Length; i++) {
if (str[i] != temp[i])
return false;
}
return true;
}
}
// Function to find lexicographic smallest
// string consisting of the string str
// as prefix
static string lexicographicallyString(string[] input,
int n, string str)
{
// Sort the given array string arr[]
Array.Sort(input);
for (int i = 0; i < n; i++) {
string temp = input[i];
// If the i-th string contains
// given string as a prefix,
// then print the result
if (is_prefix(temp, str)) {
return temp;
}
}
// If no string exists then
// return "-1"
return "-1";
}
// Driver Code
public static void Main()
{
string[] arr
= { "apple", "appe", "apl", "aapl", "appax" };
string S = "app";
int N = 5;
Console.WriteLine(
lexicographicallyString(arr, N, S));
}
}
// This code is contributed by ukasp.
Javascript
<script>
// JavaScript Program to implement
// the above approach
// Function to find the whether the
// string temp starts with str or not
function is_prefix(temp, str)
{
// Base Case
if (temp.length < str.length)
return 0;
else {
// Check for the corresponding
// characters in temp & str
for (let i = 0;
i < str.length; i++) {
if (str[i] != temp[i])
return 0;
}
return 1;
}
}
// Function to find lexicographic smallest
// string consisting of the string str
// as prefix
function lexicographicallyString(
input, n, str)
{
// Sort the given array string arr[]
input = Array.from(input).sort();
for (let i = 0; i < n; i++) {
let temp = input[i];
// If the i-th string contains
// given string as a prefix,
// then print the result
if (is_prefix(temp, str)) {
return temp;
}
}
// If no string exists then
// return "-1"
return "-1";
}
// Driver Code
let arr = ["apple", "appe", "apl",
"aapl", "appax"];
let S = "app";
let N = 5;
document.write(lexicographicallyString(
arr, N, S));
// This code is contributed by Potta Lokesh
</script>
appax
Complejidad de tiempo: O(M*K*N*log N), donde K es la longitud máxima de la string en la array arr[] .
Espacio Auxiliar: O(N)
Otro enfoque: el enfoque anterior también se puede optimizar utilizando la estructura de datos Trie insertando todas las strings dadas en Trie y luego verificando la primera string que existe en Trie que tiene el prefijo S .
Complejidad temporal: O(M*N)
Espacio auxiliar: O(N)