Dadas dos strings (de letras minúsculas), un patrón y una string. La tarea es ordenar las strings según el orden definido por el patrón. Se puede suponer que el patrón tiene todos los caracteres de la string y que todos los caracteres del patrón aparecen solo una vez.
Ejemplos:
Input : pat = "bca", str = "abc" Output : str = "bca" Input : pat = "bxyzca", str = "abcabcabc" Output : str = "bbbcccaaa" Input : pat = "wcyuogmlrdfphitxjakqvzbnes", str = "jcdokai" Output : str = "codijak"
Enfoque 1: la idea es primero contar las ocurrencias de todos los caracteres en str y almacenar estos recuentos en una array de recuento. Luego, recorra el patrón de izquierda a derecha, y para cada carácter pat[i], vea cuántas veces aparece en la array de conteo y copie este carácter tantas veces en str.
A continuación se muestra la implementación de la idea anterior.
Implementación:
C++
// C++ program to sort a string according to the
// order defined by a pattern string
#include <bits/stdc++.h>
using namespace std;
const int MAX_CHAR = 26;
// Sort str according to the order defined by pattern.
void sortByPattern(string& str, string pat)
{
// Create a count array store count of characters in str.
int count[MAX_CHAR] = { 0 };
// Count number of occurrences of each character
// in str.
for (int i = 0; i < str.length(); i++)
count[str[i] - 'a']++;
// Traverse the pattern and print every characters
// same number of times as it appears in str. This
// loop takes O(m + n) time where m is length of
// pattern and n is length of str.
int index = 0;
for (int i = 0; i < pat.length(); i++)
for (int j = 0; j < count[pat[i] - 'a']; j++)
str[index++] = pat[i];
}
// Driver code
int main()
{
string pat = "bca";
string str = "abc";
sortByPattern(str, pat);
cout << str;
return 0;
}
Java
// Java program to sort a string according to the
// order defined by a pattern string
class GFG {
static int MAX_CHAR = 26;
// Sort str according to the order defined by pattern.
static void sortByPattern(char[] str, char[] pat)
{
// Create a count array stor
// count of characters in str.
int count[] = new int[MAX_CHAR];
// Count number of occurrences of
// each character in str.
for (int i = 0; i < str.length; i++) {
count[str[i] - 'a']++;
}
// Traverse the pattern and print every characters
// same number of times as it appears in str. This
// loop takes O(m + n) time where m is length of
// pattern and n is length of str.
int index = 0;
for (int i = 0; i < pat.length; i++) {
for (int j = 0; j < count[pat[i] - 'a']; j++) {
str[index++] = pat[i];
}
}
}
// Driver code
public static void main(String args[])
{
char[] pat = "bca".toCharArray();
char[] str = "abc".toCharArray();
sortByPattern(str, pat);
System.out.println(String.valueOf(str));
}
}
// This code has been contributed by 29AjayKumar
Python3
# Python3 program to sort a string according to
# the order defined by a pattern string
MAX_CHAR = 26
# Sort str according to the order defined by pattern.
def sortByPattern(str, pat):
global MAX_CHAR
# Create a count array store count
# of characters in str.
count = [0] * MAX_CHAR
# Count number of occurrences of
# each character in str.
for i in range (0, len(str)):
count[ord(str[i]) - 97] += 1
# Traverse the pattern and print every characters
# same number of times as it appears in str. This
# loop takes O(m + n) time where m is length of
# pattern and n is length of str.
index = 0;
str = ""
for i in range (0, len(pat)):
j = 0
while(j < count[ord(pat[i]) - ord('a')]):
str += pat[i]
j = j + 1
index += 1
return str
# Driver code
pat = "bca"
str = "abc"
print(sortByPattern(str, pat))
# This code is contributed by ihritik
C#
// C# program to sort a string according to the
// order defined by a pattern string
using System;
class GFG {
static int MAX_CHAR = 26;
// Sort str according to the order defined by pattern.
static void sortByPattern(char[] str, char[] pat)
{
// Create a count array stor
// count of characters in str.
int[] count = new int[MAX_CHAR];
// Count number of occurrences of
// each character in str.
for (int i = 0; i < str.Length; i++) {
count[str[i] - 'a']++;
}
// Traverse the pattern and print every characters
// same number of times as it appears in str. This
// loop takes O(m + n) time where m is length of
// pattern and n is length of str.
int index = 0;
for (int i = 0; i < pat.Length; i++) {
for (int j = 0; j < count[pat[i] - 'a']; j++) {
str[index++] = pat[i];
}
}
}
// Driver code
public static void Main(String[] args)
{
char[] pat = "bca".ToCharArray();
char[] str = "abc".ToCharArray();
sortByPattern(str, pat);
Console.WriteLine(String.Join("", str));
}
}
/* This code contributed by PrinciRaj1992 */
Javascript
<script>
// Javascript program to sort a string according to the
// order defined by a pattern string
let MAX_CHAR = 26;
// Sort str according to the order defined by pattern.
function sortByPattern(str,pat)
{
// Create a count array stor
// count of characters in str.
let count = new Array(MAX_CHAR);
for(let i = 0; i < MAX_CHAR; i++)
{
count[i] = 0;
}
// Count number of occurrences of
// each character in str.
for (let i = 0; i < str.length; i++) {
count[str[i].charCodeAt(0) - 'a'.charCodeAt(0)]++;
}
// Traverse the pattern and print every characters
// same number of times as it appears in str. This
// loop takes O(m + n) time where m is length of
// pattern and n is length of str.
let index = 0;
for (let i = 0; i < pat.length; i++) {
for (let j = 0; j < count[pat[i].charCodeAt(0) - 'a'.charCodeAt(0)]; j++) {
str[index++] = pat[i];
}
}
}
// Driver code
let pat = "bca".split("");
let str = "abc".split("");
sortByPattern(str, pat);
document.write((str).join(""));
// This code is contributed by rag2127
</script>
bca
Complejidad temporal: O(m+n) donde m es la longitud del patrón yn es la longitud de la string.
Espacio Auxiliar: O(1)
Enfoque 2: Uso de STL
Podemos pasar un comparador a la función sort() en C++ y ordenar la string según el patrón.
C++
#include <bits/stdc++.h>
using namespace std;
// Declaring a vector globally that stores which character
// is occurring first
vector<int> position(26, -1);
//Comparator function
bool cmp(char& char1, char& char2)
{
return position[char1 - 'a'] < position[char2 - 'a'];
}
int main()
{
// Pattern
string pat = "wcyuogmlrdfphitxjakqvzbnes";
for (int i = 0; i < pat.length(); i++) {
if (position[pat[i] - 'a'] == -1)
position[pat[i] - 'a'] = i;
}
// String to be sorted
string str = "jcdokai";
// Passing a comparator to sort function
sort(str.begin(), str.end(), cmp);
cout << str;
}
Javascript
<script>
// Declaring a vector globally that stores which character
// is occurring first
let position = new Array(26).fill(-1);
//Comparator function
function cmp(char1, char2)
{
return position[char1.charCodeAt(0) - 'a'.charCodeAt(0)] - position[char2.charCodeAt(0) - 'a'.charCodeAt(0)];
}
// driver code
// Pattern
let pat = "wcyuogmlrdfphitxjakqvzbnes";
for (let i = 0; i <br pat.length; i++) {
if (position[pat.charCodeAt(i) - 'a'.charCodeAt(0)] == -1)
position[pat.charCodeAt(i) - 'a'.charCodeAt(0)] = i;
}
// String to be sorted
let str = "jcdokai";
// Passing a comparator to sort function
str = str.split("").sort(cmp).join("");
document.write(str,"</br>");
// This code is contributed by Shinjan Patra
</script>
codijak
Complejidad de tiempo: O(m+nlogn ) donde m es la longitud del patrón yn es la longitud de str.
Espacio Auxiliar: O(1)
Ejercicio : En la solución anterior, se supone que el patrón tiene todos los caracteres de str. Considere una versión modificada donde el patrón puede no tener todos los caracteres y la tarea es poner todos los caracteres restantes (en la string pero no en el patrón) al final. Los caracteres restantes deben colocarse en orden alfabético. Sugerencia: en el segundo ciclo, al aumentar el índice y colocar el carácter en str, también podemos disminuir la cuenta en ese momento. Y finalmente, recorremos la array de conteo para colocar los caracteres restantes en orden alfabético.
Este artículo es una contribución de Sanjay Khadda . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA