Dadas n strings, necesitamos ordenar esas strings de modo que cada string sea una substring de todas las strings posteriores . Si no es posible ordenar, imprima lo mismo.
Ejemplos:
Input : {"d", "zddsaaz", "ds", "ddsaa", "dds"}
Output :
d
ds
dds
ddsaa
zddsaaz
Input : {"geeks", "ee", "geeksforgeeks", "forgeeks", "ee"}
Output :
ee
ee
geeks
forgeeks
geeksforgeeks
Observación 1
Si una substring de B
Entonces longitud de A <= longitud de B
Observación 2
Si (A substring de B ) y (B substring de C)
Entonces Una substring de C
Solución
Con base en las dos observaciones anteriores, las soluciones son las siguientes
- Ordenar toda la string de la más corta a la más larga
- Valide que cada string sea una substring de la siguiente string
Si validamos que cada string es una substring de la siguiente string, según la observación 2, cada string es una substring de todas las strings que le siguen.
Java
// Java code to sort substrings
import java.util.Arrays;
import java.util.Comparator;
public class Demo {
public static void substringSort(String[] arr, int n)
{
// sort the given array from shorter string to longer
Arrays.sort(arr, new Comparator<String>() {
public int compare(String s1, String s2)
{
return Integer.compare(s1.length(), s2.length());
}
});
// validate that each string is a substring of
// the following one'
for (int i = 0; i < n - 1; i++) {
if (!arr[i + 1].contains(arr[i])) {
// the array can't be sorted
System.out.println("Cannot be sorted");
return;
}
}
// The array is valid and sorted
// print the strings in order
for (int i = 0; i < n - 1; i++) {
System.out.println(arr[i]);
}
}
public static void main(String[] args)
{
// Test 1
String[] arr1 = { "d", "zddsaaz", "ds", "ddsaa", "dds" };
substringSort(arr1, arr1.length);
// Test 2
String[] arr2 = { "for", "rof" };
substringSort(arr2, arr2.length);
}
}
Producción:
d ds dds ddsaa Cannot be sorted
Complejidad
Tiempo Complejidad: O(n log n), donde n es el número de strings.
Enfoque alternativo
Para mejorar la complejidad del tiempo, podemos usar la ordenación por conteo solo si se especifica la longitud máxima de las strings.
Suponga que ‘maxLen’ es la longitud máxima de las strings de entrada. En este caso, la solución es la siguiente:
- Crear array de longitud maxLen
- Ordene las strings de entrada de modo que la string con longitud 1 esté en primer lugar en la array
- Si hay dos o más strings que tienen la misma longitud, deben ser iguales; de lo contrario, las strings no se pueden ordenar.
- Valide que cada string sea una substring de la siguiente string más larga
C++
// C++ Program to sort substrings
#include <bits/stdc++.h>
using namespace std;
void substringSort(string arr[], int n, int maxLen)
{
int count[maxLen];
string sortedArr[maxLen];
for(int i = 0; i < maxLen; i++)
{
count[i] = 0;
sortedArr[i] = "";
}
// sort the input array
for (int i = 0; i < n; i++)
{
string s = arr[i];
int len = s.length();
if (count[len - 1] == 0)
{
sortedArr[len - 1] = s;
count[len - 1] = 1;
}
else if (sortedArr[len - 1] == s)
{
// repeated length should
// be the same string
count[len - 1]++;
}
else
{
// two different strings with the same
// length input array cannot be sorted
cout << "Cannot be sorted";
return;
}
}
// validate that each string is a
// substring of the following one
int index = 0;
// get first element
while (count[index] == 0)
index++;
int prev = index;
string prevString = sortedArr[prev];
index++;
for (; index < maxLen; index++)
{
if (count[index] != 0)
{
string current = sortedArr[index];
if (current.find(prevString) != string::npos)
{
prev = index;
prevString = current;
}
else
{
cout << "Cannot be sorted";
return;
}
}
}
// The array is valid and sorted
// print the strings in order
for (int i = 0; i < maxLen; i++)
{
string s = sortedArr[i];
for (int j = 0; j < count[i]; j++)
{
cout << s << endl;
}
}
}
// Driver code
int main()
{
int maxLen = 100;
// Test 1
string arr1[] = { "d", "zddsaaz", "ds", "ddsaa",
"dds", "dds" };
substringSort(arr1, sizeof(arr1)/sizeof(arr1[0]), maxLen);
// Test 2
string arr2[] = { "for", "rof" };
substringSort(arr2, sizeof(arr2)/sizeof(arr2[0]), maxLen);
return 0;
}
// This code is contributed by rameshtravel07.
Java
// Alternative code to sort substrings
import java.util.Arrays;
public class Demo {
public static void substringSort(String[] arr, int n, int maxLen)
{
int count[] = new int[maxLen];
String[] sortedArr = new String[maxLen];
Arrays.fill(count, 0);
Arrays.fill(sortedArr, "");
// sort the input array
for (int i = 0; i < n; i++) {
String s = arr[i];
int len = s.length();
if (count[len - 1] == 0) {
sortedArr[len - 1] = s;
count[len - 1] = 1;
}
else if (sortedArr[len - 1].equals(s)) {
// repeated length should be the same string
count[len - 1]++;
}
else {
// two different strings with the same
// length input array cannot be sorted
System.out.println("Cannot be sorted");
return;
}
}
// validate that each string is a substring
// of the following one
int index = 0;
// get first element
while (count[index] == 0)
index++;
int prev = index;
String prevString = sortedArr[prev];
index++;
for (; index < maxLen; index++) {
if (count[index] != 0) {
String current = sortedArr[index];
if (current.contains(prevString)) {
prev = index;
prevString = current;
}
else {
System.out.println("Cannot be sorted");
return;
}
}
}
// The array is valid and sorted
// print the strings in order
for (int i = 0; i < maxLen; i++) {
String s = sortedArr[i];
for (int j = 0; j < count[i]; j++) {
System.out.println(s);
}
}
}
public static void main(String[] args)
{
int maxLen = 100;
// Test 1
String[] arr1 = { "d", "zddsaaz", "ds", "ddsaa",
"dds", "dds" };
substringSort(arr1, arr1.length, maxLen);
// Test 2
String[] arr2 = { "for", "rof" };
substringSort(arr2, arr2.length, maxLen);
}
}
Python3
# Alternative code to sort substrings
def substringSort(arr, n, maxLen):
count = [0]*(maxLen)
sortedArr = [""]*(maxLen)
# sort the input array
for i in range(n):
s = arr[i]
Len = len(s)
if (count[Len - 1] == 0) :
sortedArr[Len - 1] = s
count[Len - 1] = 1
elif (sortedArr[Len - 1] == s):
# repeated length should be the same string
count[Len - 1]+=1
else:
# two different strings with the same
# length input array cannot be sorted
print("Cannot be sorted")
return
# validate that each string is a substring
# of the following one
index = 0
# get first element
while (count[index] == 0):
index+=1
prev = index
prevString = sortedArr[prev]
index+=1
while index < maxLen:
if (count[index] != 0) :
current = sortedArr[index]
if (prevString in current):
prev = index
prevString = current
else:
print("Cannot be sorted")
return
index+=1
# The array is valid and sorted
# print the strings in order
for i in range(maxLen):
s = sortedArr[i]
for j in range(count[i]):
print(s)
maxLen = 100
# Test 1
arr1 = [ "d", "zddsaaz", "ds", "ddsaa", "dds", "dds" ]
substringSort(arr1, len(arr1), maxLen)
# Test 2
arr2 = [ "for", "rof" ]
substringSort(arr2, len(arr2), maxLen)
# This code is contributed by mukesh07.
C#
// C# Program to sort substrings
using System;
class GFG
{
public static void substringSort(String[] arr,
int n, int maxLen)
{
int []count = new int[maxLen];
String[] sortedArr = new String[maxLen];
for(int i = 0; i < maxLen; i++)
{
count[i] = 0;
sortedArr[i] = "";
}
// sort the input array
for (int i = 0; i < n; i++)
{
String s = arr[i];
int len = s.Length;
if (count[len - 1] == 0)
{
sortedArr[len - 1] = s;
count[len - 1] = 1;
}
else if (ReferenceEquals(s,sortedArr[len - 1]))
{
// repeated length should
// be the same string
count[len - 1]++;
}
else
{
// two different strings with the same
// length input array cannot be sorted
Console.WriteLine("Cannot be sorted");
return;
}
}
// validate that each string is a
// substring of the following one
int index = 0;
// get first element
while (count[index] == 0)
index++;
int prev = index;
String prevString = sortedArr[prev];
index++;
for (; index < maxLen; index++)
{
if (count[index] != 0)
{
String current = sortedArr[index];
if (current.Contains(prevString))
{
prev = index;
prevString = current;
}
else
{
Console.WriteLine("Cannot be sorted");
return;
}
}
}
// The array is valid and sorted
// print the strings in order
for (int i = 0; i < maxLen; i++)
{
String s = sortedArr[i];
for (int j = 0; j < count[i]; j++)
{
Console.WriteLine(s);
}
}
}
public static void Main(String[] args)
{
int maxLen = 100;
// Test 1
String[] arr1 = { "d", "zddsaaz", "ds", "ddsaa",
"dds", "dds" };
substringSort(arr1, arr1.Length, maxLen);
// Test 2
String[] arr2 = { "for", "rof" };
substringSort(arr2, arr2.Length, maxLen);
}
}
// This code is contributed by PrinciRaj1992
Javascript
<script>
// Alternative code to sort substrings
function substringSort(arr, n, maxLen)
{
let count = new Array(maxLen);
let sortedArr = new Array(maxLen);
count.fill(0);
for(let i = 0; i < maxLen; i++)
{
sortedArr[i] = "";
}
// sort the input array
for (let i = 0; i < n; i++) {
let s = arr[i];
let len = s.length;
if (count[len - 1] == 0) {
sortedArr[len - 1] = s;
count[len - 1] = 1;
}
else if (sortedArr[len - 1] == s) {
// repeated length should be the same string
count[len - 1]++;
}
else {
// two different strings with the same
// length input array cannot be sorted
document.write("Cannot be sorted" + "</br>");
return;
}
}
// validate that each string is a substring
// of the following one
let index = 0;
// get first element
while (count[index] == 0)
index++;
let prev = index;
let prevString = sortedArr[prev];
index++;
for (; index < maxLen; index++) {
if (count[index] != 0) {
let current = sortedArr[index];
if (current.includes(prevString)) {
prev = index;
prevString = current;
}
else {
document.write("Cannot be sorted");
return;
}
}
}
// The array is valid and sorted
// print the strings in order
for (let i = 0; i < maxLen; i++) {
let s = sortedArr[i];
for (let j = 0; j < count[i]; j++) {
document.write(s + "</br>");
}
}
}
let maxLen = 100;
// Test 1
let arr1 = [ "d", "zddsaaz", "ds", "ddsaa",
"dds", "dds" ];
substringSort(arr1, arr1.length, maxLen);
// Test 2
let arr2 = [ "for", "rof" ];
substringSort(arr2, arr2.length, maxLen);
// This code is contributed by decode2207.
</script>
Producción:
d ds dds dds ddsaa zddsaaz Cannot be sorted
Publicación traducida automáticamente
Artículo escrito por salmayehia y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA