8
$\begingroup$

How can I write a function that checks whether the characters in the first string are in the same order as in the second string?

Examples:

f["ABCDE", "ABC"]
(* True *)

f["ACBDE", "ABC"]
(* False *)
$\endgroup$
2
  • $\begingroup$ Haven't yet figured out how to make it work, but I suspect that SequenceAlignment could be used here. $\endgroup$
    – lericr
    Sep 20, 2023 at 18:14
  • 2
    $\begingroup$ I'm glad this seemingly simple question led to many different approaches, thanks to all who contributed! $\endgroup$
    – Suite401
    Sep 20, 2023 at 22:44

8 Answers 8

8
$\begingroup$
ClearAll[alignedQ]

alignedQ = #2 == LongestCommonSequence @ ## &;

Examples:

exampleinputs = {{"ABCDE", "ABC"}, {"ACBDE", "ABC"}, {"ABCDE", "ABCE"}, 
 {"MISSOURI SOUTHERN STATE", "MOS"}, {"MISSOURI SOUTHERN STATE", "MSO"}, 
 {"MISSOURI SOUTHERN STATE", "RTM"}, 
 {"MISSOURI SOUTHERN STATE", "MISSOURI SOUTHERN STATE"}, 
 {"MISSOURI SOUTHERN STATE", "MISSOURI SOUHTERN STATE"}, 
 {"Hello Mathematica Stack Exchange",  "ica"}};


Grid[{##, alignedQ @ ##} & @@@ exampleinputs]
str1 str2 alignedQ[str1,str2]
"ABCDE" "ABC" True
"ACBDE" "ABC" False
"ABCDE" "ABCE" True
"MISSOURI SOUTHERN STATE" "MOS" True
"MISSOURI SOUTHERN STATE" "MSO" True
"MISSOURI SOUTHERN STATE" "RTM" False
"MISSOURI SOUTHERN STATE" "MISSOURI SOUTHERN STATE" True
"MISSOURI SOUTHERN STATE" "MISSOURI SOUHTERN STATE" False
"Hello Mathematica Stack Exchange" "ica" True

Alternatively,

ClearAll[alignedQ2]

alignedQ2 = StringMatchQ[#, StringRiffle[Characters@#2, Table["*", 3]]] &;


alignedQ2 @@@ exampleinputs == alignedQ @@@ exampleinputs
True
$\endgroup$
2
  • 1
    $\begingroup$ nice! I wish I'd remembered LongestCommonSequence! $\endgroup$
    – lericr
    Sep 20, 2023 at 22:34
  • 1
    $\begingroup$ Nice and short solution! I always learn something new watching your contributions :-) $\endgroup$ Sep 21, 2023 at 0:22
6
$\begingroup$

This one passes all of the tests I've seen so far, but I'm still not actually sure it will work for what you want to use it for.

SameOrderQ[full_, abbr_] :=
  StringContainsQ[
    StringJoin[DeleteCases[SequenceAlignment[full, abbr], _List]], 
    abbr]

Tests:

SameOrderQ["ABCDE", "ABC"]
(*True*)

SameOrderQ["ACBDE", "ABC"]
(*False*)

SameOrderQ["ABCDE", "ABCE"]
(*True*)

SameOrderQ["MISSOURI SOUTHERN STATE", "MOS"]
(*True*)

SameOrderQ["MISSOURI SOUTHERN STATE", "MSO"]
(*True*)

SameOrderQ["MISSOURI SOUTHERN STATE", "RTM"]
(*False*)

SameOrderQ["MISSOURI SOUTHERN STATE", "MISSOURI SOUTHERN STATE"]
(*True*)

SameOrderQ["MISSOURI SOUTHERN STATE", "MISSOURI SOUHTERN STATE"]
(*False*)

SameOrderQ["Hello Mathematica Stack Exchange", "ica"]
(*True*)
$\endgroup$
0
5
$\begingroup$

The following gives the desired outputs as described in the OP

f[a_, b_] := StringContainsQ[a, b]
f["ABCDE", "ABC"]
f["ABCDE", "ABC"]
f["ACBDE", "ABC"]

true

true

false

Checking some more cases for completeness:

f["ACBDE", "BDE"]

true

f["ABCDE", "ABCE"]

false

f["Hello Mathematica Stack Exchange", "ica"]

true

$\endgroup$
7
  • 1
    $\begingroup$ thank you for the prompt response $\endgroup$
    – Suite401
    Sep 20, 2023 at 16:44
  • $\begingroup$ I just saw your solution fails with {"MISSOURI SOUTHERN STATE", "MOS"}? This appears to be more complicated as first sight! $\endgroup$
    – Suite401
    Sep 20, 2023 at 17:14
  • $\begingroup$ @Suite401 thanks for the comment. In your example I find it weird that you were expecting a True output to be honest. S is before the O in MISSOURI SOUTHERN STATE $\endgroup$
    – bmf
    Sep 20, 2023 at 17:22
  • $\begingroup$ yes, was hoping for "True" - any thoughts for a revision? $\endgroup$
    – Suite401
    Sep 20, 2023 at 17:26
  • 1
    $\begingroup$ @Suite401 ohhh I see. so you are, also, interested in jumps as well, right? $\endgroup$
    – bmf
    Sep 20, 2023 at 17:52
5
$\begingroup$

Another way to do this using StringPosition:

f = UnsameQ[StringPosition[#1, #2], {}] &;

Checking my mate @bmf's latest case:

f["Hello Mathematica Stack Exchange", "ica"]

(*True*)

Edit Considering everything discussed with my mate @bmf and using the details provided by the author of the OP, my proposal is the following:

ContainsWithSkips[str_String, pattern_String] := 
Module[{regexPattern = 
        ".*" <> StringJoin[Riffle[Characters[pattern], ".*"]] <> ".*"}, 
       StringMatchQ[str, RegularExpression[regexPattern], IgnoreCase -> True]]

Testing ContainsWithSkips:

ContainsWithSkips["ABCDE", "ABCE"]

(*True*)

ContainsWithSkips["MISSOURI SOUTHERN STATE", "MOS"]

(*True*)
ContainsWithSkips["ACBDE", "ABC"]

(*False*)

ContainsWithSkips["Hello Mathematica Stack Exchange", "ica"]

(*True*)
$\endgroup$
5
  • 1
    $\begingroup$ Nice one as well. Check the comment section in my answer as the author of the OP is interested in something that is a bit extra ;) $\endgroup$
    – bmf
    Sep 20, 2023 at 17:56
  • $\begingroup$ Hi mate! I see, it seems that the author of the OP wants something more complicated. $\endgroup$ Sep 20, 2023 at 18:01
  • 1
    $\begingroup$ f = UnsameQ[StringPosition[#1, #2], {}] &; also fails the Missouri test :/ $\endgroup$
    – Suite401
    Sep 20, 2023 at 18:06
  • $\begingroup$ I understand, but then the example f["ABCDE", "ABCE"] also fails, since "ABCE" is a substring that has a jump. $\endgroup$ Sep 20, 2023 at 18:12
  • $\begingroup$ Yes, would hope for a True with {"ABCDE","ABCE"} $\endgroup$
    – Suite401
    Sep 20, 2023 at 18:17
5
$\begingroup$

Using test data from @kglr and reinventing longest common sequence using StringExpression:

lcss[{main_String, seq_String}] := 
 Module[{expr = 
    StringExpression @@ Riffle[Characters@seq, BlankNullSequence[]] //
       Append[BlankNullSequence[]] // Prepend[BlankNullSequence[]]},
  StringMatchQ[main, expr]
  ]

exampleinputs = {{"ABCDE", "ABC"}, {"ACBDE", "ABC"}, {"ABCDE", 
    "ABCE"}, {"MISSOURI SOUTHERN STATE", 
    "MOS"}, {"MISSOURI SOUTHERN STATE", 
    "MSO"}, {"MISSOURI SOUTHERN STATE", 
    "RTM"}, {"MISSOURI SOUTHERN STATE", 
    "MISSOURI SOUTHERN STATE"}, {"MISSOURI SOUTHERN STATE", 
    "MISSOURI SOUHTERN STATE"}, {"Hello Mathematica Stack Exchange", 
    "ica"}};

lcss /@ exampleinputs

{True, False, True, True, True, False, True, False, True}

$\endgroup$
5
$\begingroup$
foo[{a_, b_}] := 
 MemberQ[Characters @ b] @ Subsets[Characters @ a, {StringLength @ b}]

foo /@ exampleinputs

{True, False, True, True, True, False, True, False, True}

exampleinputs like accepted answer (kglr)

$\endgroup$
5
$\begingroup$
StringContainsQ[___~~"A"~~___~~"B"~~___~~"C"~~___]/@{"ABCDE","ACBDE","EABCD"}

(* {True,False,True} *)
StringContainsQ[___~~"M"~~___~~"O"~~___~~"S"~~___]/@{"MISSOURI SOUTHERN STATE",
  "MISSOURI ZOUTHERN MATE"}

(* {True,False} *)

Regular Expression

StringMatchQ[RegularExpression@StringTemplate[StringRiffle[ConstantArray[".*",
  3+1],"``"]]["A","B","C"]]/@{"ABCDE","ACBDE","EABCD"}

(* {True,False,True} *)
 StringMatchQ[RegularExpression@StringTemplate[StringRiffle[ConstantArray[".*",
  3+1],"``"]]["M","O","S"]]/@{"MISSOURI SOUTHERN STATE","MISSOURI ZOUTHERN MATE"}

(* {True,False} *)
StringMatchQ[RegularExpression@StringTemplate[StringRiffle[ConstantArray[".*",
  5+1],"``"]]["M","I","O" ,"R","S","E"]]/@{"MISSOURI SOUTHERN STATE",
  "MISSOURI ZOUTHERN MATE"}

(* {True,False} *)
$\endgroup$
2
$\begingroup$

Say s1 and s2 are strings where StringLength[s1]>=StringLength[s2].

First we check if the characters of s2 appear in s1.

Now we determine the first position of the first character of s2 in s1 and store it in p.

Next we determine the first position of the the next character of s2 in s1 that is larger than p. If there is none, the test fails. Otherwise the position is stored in p. This is repeated over the characters of s2.

test[s1_, s2_] := 
 Module[{pos, cs1 = Characters[s1], cs2 = Characters[s2], p = 0, 
   res = True},
  If[! SubsetQ[cs1, cs2], Print["s2 not contained in s1"]; Return[]];
  pos = StringPosition[s1, #] & /@ cs2;
  pos = Map[#[[All, 1]] &, pos, 1];
  Do[If[Max[pos[[i]]] < p, res = False;Break[]]; 
   p = First[Select[pos[[i]], Function[x, x > p]]];
   , {i, Length[pos]}];
  res
  ]

Some test cases:

s1="MISSOURI SOUTHERN STATE"

test[s1,"MSO"]
True
test[s1, "RTM"]
False

test[s1, "MISSOURI SOUTHERN STATE"]
True

But if we exchange T and H

test[s1, "MISSOURI SOUHTERN STATE"]
False
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.