LeetCode 14. Longest Common Prefix (LaTeX)

Write a function to find the longest common prefix string amongst an array of strings.

If there is no common prefix, return an empty string "".

Example

Example 1:

Input: ["flower","flow","flight"]
Output: "fl"

Example 2:

Input: ["dog","racecar","car"]
Output: ""
Explanation: There is no common prefix among the input strings.

Notes

All given inputs are in lowercase letters a-z.

Solution

This solution is probably too long, since there are many debug outputs. The core approach is still to use a nested loop to look at each character in every string.

\documentclass{article}
\usepackage[T1]{fontenc}
\usepackage{datetime2}
\usepackage{expl3}

\begin{document}
\setlength{\parindent}{0cm}

\ExplSyntaxOn

\tl_new:N \g_tmpc_tl
\int_new:N \g_tmpc_int
\int_new:N \g_tmpd_int
\tl_new:N \g_result_tl % where result is stored

\cs_generate_variant:Nn \tl_greplace_all:Nnn {NVn}

\cs_set:Npn \longest_common_prefix:n #1 {
    \clist_gset:Nn \g_tmpa_clist {#1} % create a new list of tokens
    \par token~list:~\cs_meaning:N \g_tmpa_clist % debug line

    \clist_gclear:N \g_tmpb_clist % prepare a list of strings
    % construct a list of strings
    \clist_map_variable:NNn \g_tmpa_clist \g_tmpa_tl
        {
        \exp_args:NNV \str_set:Nn \l_tmpa_str { \g_tmpa_tl }
        \clist_put_right:NV \g_tmpb_clist {\l_tmpa_str}
        }    
    \par string~list:~\cs_meaning:N \g_tmpb_clist % debug line

    % find the smallest length in the list of string
    \int_gset:Nn \g_tmpa_int {\c_max_int} % initialize smallest length variable
    \seq_gclear:N \g_tmpa_seq % clear length array
    \clist_map_variable:NNn \g_tmpb_clist \g_tmpa_tl
        {
        \exp_args:NNx \int_gset:Nn \g_tmpb_int {\str_count:N \g_tmpa_tl}
        \exp_args:NNx \int_gset:Nn \g_tmpa_int {\int_min:nn {\g_tmpa_int} {\g_tmpb_int}}
        }
    \par length~of~shortest~string:~\int_use:N \g_tmpa_int % debug line

    \exp_args:NNx \int_gset:Nn \g_tmpb_int {\clist_count:N \g_tmpb_clist}
    \par number~of~strings:~\int_use:N \g_tmpb_int % debug line
    \tl_gclear:N \g_tmpa_tl % where result is stored
    \int_gset:Nn \g_tmpc_int {1} % loop variable 1

    \bool_gset:Nn \g_tmpa_bool {\c_true_bool} % loop control variable

    \bool_while_do:Nn {\g_tmpa_bool}
        {
        \int_gset:Nn \g_tmpd_int {1} % loop variable 2
        \tl_gclear:N \g_tmpb_tl % this is used to detect if all characters are the same
        \par round~\int_use:N \g_tmpc_int :~
        \int_do_until:nNnn {\g_tmpd_int} {>} {\g_tmpb_int}
            {
            \exp_args:NNx \str_set:Nn \l_tmpa_str {\clist_item:Nn \g_tmpb_clist {\g_tmpd_int}}
            \tl_gset:Nx \g_tmpc_tl {\str_item:Nn \l_tmpa_str {\g_tmpc_int}}
            \tl_use:N \g_tmpc_tl % debug output
            \tl_gput_right:NV \g_tmpb_tl {\g_tmpc_tl}
            \int_gincr:N \g_tmpd_int % increment loop variable
            }
        \ (\tl_use:N \g_tmpb_tl) % debug output

        % if nothing is extracted, exit right away
        \bool_if:nTF {\tl_if_empty_p:N \g_tmpb_tl} {\bool_gset:Nn \g_tmpa_bool {\c_false_bool}}
            {
            % take the first character out
            \tl_gset:Nx \g_tmpc_tl {\tl_head:N \g_tmpb_tl}
            % reduce all identical characters
            \tl_greplace_all:NVn \g_tmpb_tl {\g_tmpc_tl} {}
            \par after~replacement:~\tl_use:N \g_tmpb_tl % debug line
            \bool_if:nTF {\tl_if_empty_p:N \g_tmpb_tl}
                {% if there is nothing left, put this into result
                % because all letters are the same
                \tl_gput_right:NV \g_tmpa_tl {\g_tmpc_tl}
                }
                {
                % if there is something left, it means the loop needs to stop
                \bool_gset:Nn \g_tmpa_bool {\c_false_bool}
                }
            }

        \str_set:NV \l_tmpa_str {\clist_item:Nn \g_tmpb_clist {\g_tmpc_int}}% extract the current string
        \int_gincr:N \g_tmpc_int % increment loop variable

        % set exit condition if the loop ends
        \int_compare:nNnTF {\g_tmpc_int} {>} {\g_tmpa_int}
            { \bool_gset:Nn \g_tmpa_bool {\c_false_bool} } {}
        }

        \tl_set_eq:NN \g_result_tl \g_tmpa_tl
}

\longest_common_prefix:n {abcd, abc, ab}
\par \textbf{result: \g_result_tl}
\longest_common_prefix:n {flower,flow,flight}
\par \textbf{result: \g_result_tl}
\longest_common_prefix:n {dog,racecar,car}
\par \textbf{result: \g_result_tl}

\ExplSyntaxOff

\DTMnow

\end{document}

Output

The three test cases in the code are:

\longest_common_prefix:n {abcd, abc, ab}
\par \textbf{result: \g_result_tl}
\longest_common_prefix:n {flower,flow,flight}
\par \textbf{result: \g_result_tl}
\longest_common_prefix:n {dog,racecar,car}
\par \textbf{result: \g_result_tl}

The output is shown as below.

token list: macro:->abcd,abc,ab
string list: macro:->abcd,abc,ab
length of shortest string: 2
number of strings: 3
round 1: aaa (aaa)
after replacement:
round 2: bbb (bbb)
after replacement:
result:ab
token list: macro:->flower,flow,flight
string list: macro:->flower,flow,flight
length of shortest string: 4
number of strings: 3
round 1: fff (fff)
after replacement:
round 2: lll (lll)
after replacement:
round 3: ooi (ooi)
after replacement: i
result:fl
token list: macro:->dog,racecar,car
string list: macro:->dog,racecar,car
length of shortest string: 3
number of strings: 3
round 1: drc (drc)
after replacement: rc
result:
2020-06-10 17:21:23-04:00