LeetCode 344: Reverse String (LaTeX)
05 Jun 2020Write a function that reverses a string. The input string is given as an array of characters char[]`.
Example
Example 1:
Input: ["h","e","l","l","o"]
Output: ["o","l","l","e","h"]
Example 2:
Input: ["H","a","n","n","a","h"]
Output: ["h","a","n","n","a","H"]
Notes
- The original question requires in-place modification with $O(1)$ memory. Since LaTeX does not have proper support for ordered lists, this requirement is discarded.
Solution
\documentclass{article}
\usepackage[T1]{fontenc}
\usepackage{expl3}
\begin{document}
\ExplSyntaxOn
\cs_set:Npn \reverse_string:n #1 {
% convert token list to string
\str_set:Nn \l_tmpa_str {#1}
% use a sequence to save the string
\seq_gclear:N \g_tmpa_seq
% store each character in \l_tmpa_str in \l_tmpa_seq
% use \exp_args:NV to expand the first argument
\exp_args:NV \str_map_variable:nNn { \l_tmpa_str } { \l_tmpb_str }
{ \seq_gput_right:NV \g_tmpa_seq \l_tmpb_str }
% pop each element in \l_tmpa_str from right side
\bool_do_while:nn {
% reverse the value of \seq_if_empty_p:N
\bool_if:nTF {\seq_if_empty_p:N \g_tmpa_seq} {\c_false_bool} {\c_true_bool}
}
{
\seq_gpop_right:NN \g_tmpa_seq \l_tmpa_tl
% generate output
\tl_use:N \l_tmpa_tl
}
}
\newcommand{\reversestring}[1]{\reverse_string:n {#1}}
\ExplSyntaxOff
\reversestring{abcde12345}
\end{document}
Output
54321edcba
- There really isn’t much choice when it comes to reversing a string in LaTeX, because LaTeX does not provide a way to read something “from behind”. In this solution, I decide to construct a stack with
l3seqto reverse the order of characters. Another way of doing so may be using an integer loop with\str_item:nn. But this macro seems to work by discarding characters before the desired index, so the performance may be bad. - The performance of this code isn’t great either. I tried to reverse 10,000 characters, and it takes around 10 seconds to finish. I think it is because the implementation of
l3seqisn’t very efficient either. - I guess the lesson learned is that don’t reverse long strings in LaTeX. Do it somewhere else!
Tips for LaTeX programming
- Due to the expansion mechanism of LaTeX, it is very inconvenient for a macro to return value(s).
- Therefore, if the intended return value is to be put into text, simply
usethe result so that it is inserted into the output stream. - If the intended return value is to be used by another macro, store this value into a global variable and use the value.
Updates
LaTeX3 has already provided a command to reverse tokens (\tl_reverse:n), which allows us to write a simpler program like so. However, after
some experiments, I find out that this is no faster than my own version. This may imply that the internal implementation of this function
is similar.
\documentclass{article}
\usepackage[T1]{fontenc}
\usepackage{expl3}
\begin{document}
\ExplSyntaxOn
\cs_set:Npn \reverse_string:n #1 {
\tl_reverse:n {#1}
}
\newcommand{\reversestring}[1]{\reverse_string:n {#1}}
\ExplSyntaxOff
\reversestring{abcde12345}
\end{document}
More Updates (07/03/2020)
It is possible to use l3intarray package to facilitate string reversal. The following code is capable of reversing 10,000 characters in no time.
However, the drawbacks of this method include:
- Big memory consumption: each character is probably saved as 4-byte integer.
- There is a certain limit on the size of
l3intarray. According to the documentation, the length of array can only be around \(4 \times 10^6\). On LuaTeX, the length can be longer. (But who needs this solution if there is Lua support anyways.)
\documentclass{article}
\usepackage[a4paper]{geometry}
\usepackage[T1]{fontenc}
\usepackage{mathptmx}
\usepackage{amsmath, amssymb}
\usepackage{tasks}
\usepackage{datetime2}
\usepackage{expl3}
\begin{document}
\ExplSyntaxOn
\int_new:N \l_ind_int
\cs_new:Npn \to_ascii:n #1 {
\int_eval:n {`#1}
}
\cs_generate_variant:Nn \intarray_gset:Nnn {Nnx}
\cs_new:Npn \fill_intarr:n #1 {
\intarray_gset:Nnx \g_tmpa_intarr {\l_ind_int} {\to_ascii:n {#1}}
\int_incr:N \l_ind_int
}
\cs_new:Npn \reverse_str:n #1 {
\str_set:Nn \l_tmpa_str {#1}
\cs_if_exist:NT \g_tmpa_intarr {
\cs_gset_eq:NN \g_tmpa_intarr \undefined
}
\intarray_new:Nn \g_tmpa_intarr {\str_count:N \l_tmpa_str}
\int_set:Nn \l_ind_int {1}
\str_map_function:NN \l_tmpa_str \fill_intarr:n
\int_set:Nn \l_tmpa_int {\str_count:N \l_tmpa_str}
\int_do_while:nNnn {\l_tmpa_int} > {0} {
\int_set:Nn \l_tmpb_int {\intarray_item:Nn \g_tmpa_intarr {\l_tmpa_int}}
\exp_args:Nx \tl_to_str:n {\char_generate:nn {\l_tmpb_int}{12}}
\int_decr:N \l_tmpa_int
}
}
\newcommand{\reversestr}[1]{
\reverse_str:n {#1}
}
\ExplSyntaxOff
\par\DTMNow
\end{document}