# 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
% 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