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 *)
Improve this question
$\endgroup$
2
  • $\begingroup$ Haven't yet figured out how to make it work, but I suspect that SequenceAlignment could be used here. $\endgroup$ Commented 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$ Commented Sep 20, 2023 at 22:44

8 Answers 8

Reset to default
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
Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ nice! I wish I'd remembered LongestCommonSequence! $\endgroup$ Commented Sep 20, 2023 at 22:34
  • 1
    $\begingroup$ Nice and short solution! I always learn something new watching your contributions :-) $\endgroup$ Commented 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*)
Improve this answer
$\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

Improve this answer
$\endgroup$
7
  • 1
    $\begingroup$ thank you for the prompt response $\endgroup$ Commented 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$ Commented 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$ Commented Sep 20, 2023 at 17:22
  • $\begingroup$ yes, was hoping for "True" - any thoughts for a revision? $\endgroup$ Commented Sep 20, 2023 at 17:26
  • 1
    $\begingroup$ @Suite401 ohhh I see. so you are, also, interested in jumps as well, right? $\endgroup$ Commented 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*)
Improve this answer
$\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$ Commented Sep 20, 2023 at 17:56
  • $\begingroup$ Hi mate! I see, it seems that the author of the OP wants something more complicated. $\endgroup$ Commented Sep 20, 2023 at 18:01
  • 1
    $\begingroup$ f = UnsameQ[StringPosition[#1, #2], {}] &; also fails the Missouri test :/ $\endgroup$ Commented 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$ Commented Sep 20, 2023 at 18:12
  • $\begingroup$ Yes, would hope for a True with {"ABCDE","ABCE"} $\endgroup$ Commented 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}

Improve this answer
$\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)

Improve this answer
$\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} *)
Improve this answer
$\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
Improve this answer
$\endgroup$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.