Dans cet article, je vais résoudre le problème de la conversion d'une chaîne de caractères linéaire en une chaîne de caractères alternée (zigzag).
Le but est de résoudre ce problème à l'aide de deux méthodes. La première sera volontairement peu efficace, tandis que la deuxième sera optimisée.
Ensuite, nous comparerons les deux méthodes.
La difficulté de ce problème, selon le site LeetCode, est moyenne.
The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)
And then read line by line: "PAHNAPLSIIGYIR"
Write the code that will take a string and make this conversion given a number of rows:
string convert(string s, int numRows);
Contraintes :
1 <= s.length <= 1000s consists of English letters (lower-case and upper-case), ',' and '.'.1 <= numRows <= 1000Dans cette méthode, nous explorons une approche basée sur un masque. Ce masque est représenté par une matrice.
En plus, nous utilisons une autre classe qui permet de générer les indices dans la matrice représentant la chaîne de caractères sous forme matricielle.
Cette approche est plus visuelle et repose sur l’abstraction à l’aide de classes telles que indexer.
struct Pair
{
int a, b;
};
template<char c = '\0'>
class matrix
{
private:
vector<vector<char>> data;
public:
matrix(int x, int y)
{
this->data = vector<vector<char>>(x);
for (int i = 0; i < x; i++)
{
this->data[i] = vector<char>(y, c);
}
}
char& operator ()(int a, int b)
{
return this->data[a][b];
}
char& operator [](Pair index)
{
return this->operator()(index.a, index.b);
}
};
struct indexer
{
private:
int rows, rows_2;
public:
indexer(int rows) : rows(rows)
{
this->rows_2 = (this->rows - 1) * 2;
}
Pair operator[](int index)
{
return this->direct(index);
}
private:
Pair direct(int index)
{
if (this->rows == 1) return Pair {index, 0} ;
int div = index / this->rows_2, mod = index % this->rows_2;
if (mod < this->rows)
{
return Pair {(this->rows - 1) * div, mod % this->rows};
}
else
{
int x = mod % this->rows + 1;
return Pair {x + (this->rows - 1) * div, this->rows - 1 - x};
}
}
};
class Solution {
public:
string convert(string s, int numRows) {
indexer i(numRows);
int x = numRows, y;
if (numRows == 1)
{
y = s.size();
}
else
{
int div = s.size() / (2 * (numRows - 1)), mod = s.size() % (2 * (numRows - 1));
int b = mod == 0 ? 0 : mod <= numRows ? 1 : 1 + mod - numRows;
y = div * (numRows - 1) + b;
}
matrix data(y, x);
for (int j = 0; j < s.size(); j++)
{
data[i[j]] = s[j];
}
string ret(s.size(), '\0');
int index = 0;
for (int j = 0; j < x; j++)
{
for (int k = 0; k < y; k++)
{
if (data[{k, j}])
{
ret[index++] = data[{k, j}];
}
}
}
return ret;
}
};
Cette solution, contrairement à la première, se base sur des opérations plus élémentaires. En considérant qu’à partir de la première ligne jusqu’à l’avant-dernière ligne, on copie deux éléments par période.
Nous itérons ligne par ligne en affectant les caractères de la chaîne d’origine selon une période de 2 * (nombre de lignes - 1).
class Solution {
public:
string convert(string s, int numRows) {
unsigned int string_size = s.size();
string converted_string(string_size, 'a');
unsigned int step = (numRows == 1) ? 1 : 2 * (numRows - 1);
unsigned int converted_string_index = 0;
const unsigned int upper_bound = numRows - 1, lower_bound = 0;
for (unsigned int i = 0; i < numRows; i++)
{
unsigned int index = i;
while ((index < string_size) & (converted_string_index < string_size))
{
converted_string[converted_string_index++] = s[index];
if ((i > lower_bound) & (i < upper_bound))
{
unsigned int temporary_index = index + step - 2 * i;
if (temporary_index < string_size)
converted_string[converted_string_index++] = s[temporary_index];
}
index += step;
}
}
return converted_string;
}
};
Par rapport à la première, la deuxième solution offre un gain de performance important en termes de temps d’exécution dans l’environnement défini par la plateforme LeetCode.
Les temps d’exécution et la consommation mémoire pour les deux solutions sont les suivants :
31 ms21.6 MB2 ms18.0 MBLa différence de performance et de consommation de ressources provient du fait que la première méthode utilise une matrice représentant la forme du zigzag.
Cette matrice contient de nombreux espaces vides. Ainsi, pour de longues chaînes de caractères et un nombre élevé de lignes, le nombre de cases inutilisées augmente, ce qui entraîne une consommation mémoire plus importante et un temps d’exécution plus élevé, car de nombreux éléments inutiles sont parcourus.
L'approche directe peut parfois être plus simple et plus efficace que l'utilisation de mécanismes d'abstraction complexes du langage C++. Toutefois, il ne faut pas en conclure que le problème est dû au langage lui-même, mais plutôt à la méthode d'abstraction employée.
Dès lors que des méthodes plus élémentaires peuvent être utilisées, il est pertinent de les envisager afin de garantir de meilleures performances.
Toutefois, il reste essentiel de bien choisir le niveau d'abstraction ainsi que le code sous-jacent, afin d'assurer de bonnes performances globales.