28
\$\begingroup\$

Given strings X and Y, determine whether X is a subsequence of Y. The empty string is regarded as a subsequence of every string. (E.g., '' and 'anna' are subsequences of 'banana'.)

Input

  • X, a possibly-empty case-sensitive alphanumeric string
  • Y, a possibly-empty case-sensitive alphanumeric string

Output

  • True or False (or equivalents), correctly indicating whether X is a subsequence of Y.

I/O examples

X      Y        output

''     'z00'    True
'z00'  'z00'    True 
'z00'  '00z0'   False
'aa'   'anna'   True
'anna' 'banana' True
'Anna' 'banana' False

Criteria

  • The shortest program wins, as determined by the number of bytes of source code.

Example programs

\$\endgroup\$
3
  • 1
    \$\begingroup\$ Why is 'anna' substr of 'banana'? \$\endgroup\$
    – kaoD
    Apr 26, 2012 at 5:04
  • 7
    \$\begingroup\$ @kaoD - anna is a subsequence (but not a substring) of banana. String X is a subsequence of string Y just if X can be obtained from Y by deleting zero or more of the elements of Y; e.g., deleting the b and the second a from banana gives anna. \$\endgroup\$
    – r.e.s.
    Apr 26, 2012 at 13:33
  • 5
    \$\begingroup\$ This has about a single solution in every scripting language offering regex that's both trivial to see and impossible to golf further. \$\endgroup\$
    – Joey
    Apr 27, 2012 at 14:50

68 Answers 68

2
\$\begingroup\$

Regex (PCRE2 v10.35+), 25 bytes

^((.)(?*.*
(\3?+.*\2)))*

Attempt This Online!

Takes input as X followed by Y, delimited by a newline.

This abuses molecular lookahead (?*...) to save a byte. Instead of using a lazy quantifier .*? to advance only as far as necessary to find the next matching character, it greedily lets the regex engine do all the work by backtracking until it is able to match all of X in Y (or fail to, after trying all possibilities).

This beats mbomb007's Retina answer by 1 byte, though not when ported to .NET (in that it is 29 bytes – see below).

Regex (Perl / PCRE / Java), 26 bytes

^((.)(?=.*
(\3?+.*?\2)))*

Try it online! - Perl
Try it online! - PCRE1
Try it online! - PCRE2
Try it online! - Java

^                 # Anchor to start of string X
(
    (.)           # \2 = next character from X (starting at its start)
    (?=           # Atomic lookahead
        .*¶       # Skip to the beginning of string Y
        (         # \3 = concatenation of the following:
            \3?+  # previous value of \3, if set
            .*?   # Advance by as little as possible (minimum zero) to make the
                  # following match:
            \2    # Match the character we captured in \2
        )
    )
)*                # Iterate the above as many times as possible
¶                 # Assert that after doing the above, we've reached a newline,
                  # meaning the loop processed all of string X.

Taking the arguments in the opposite order takes 28 bytes:

((.)(?=.*
(\3?+\2)).*)*
\3?$

Try it online! - PCRE2

Regex (Perl / PCRE / Java / .NET), 29 bytes

^((.)(?=.*
((?>\3?).*?\2)))*

Try it online! - Perl
Try it online! - PCRE1
Try it online! - PCRE2
Try it online! - Java
Try it online! - .NET

The uses an atomic group (?>\3?) instead of a possessive quantifier \3?+ to add .NET compatibility.

Regex (.NET), 31 bytes

(?<=(.)*)
(.*(?<-1>\1))*(?(1)^)

Try it online!

As a matter of curiosity (even though it doesn't beat the group-building method), here is a version using .NET's Balancing Groups feature.

(?<=(.)*)      # In a lookbehind, push each character of string X onto the \1
               # stack, going from right to left. There is no need to use a "^"
               # anchor, because the lookbehind is atomic and will lock in its
               # first greedy full match.
¶              # Assert that the next character is a newline, meaning that the
               # above processed the entirity of string X.
(
    .*         # Skip however many characters as needed to match the following:
    (?<-1>\1)  # Pop a capture off the \1 stack and match it. This is iterated
               # from left to right.
)*             # Iterate the above as many times as possible.
(?(1)^)        # Assert that the \1 stack is now empty (by asserting that if it
               # isn't, then we're at the start of the string – which is
               # impossible because we have at the very least matched a newline).

Regex (Perl / PCRE / Java / Pythonregex / Ruby / .NET), 33 bytes

^((.)(?=.*
(?=(\4?))(\3.*?\2)))*

Try it online! - Perl
Try it online! - PCRE1
Try it online! - PCRE2
Try it online! - Java
Try it online! - Python import regex
Try it online! - Ruby

Try it online! - .NET

Copies the capture back and forth between \3 and \4 to avoid use of nested backreferences, adding Python and Ruby support (and as the lookahead is atomic, it's also another way of adding .NET support).

\$\large\textit{Anonymous functions}\$

Julia, 52 51 50 bytes

-1 byte thanks to MarcMush
-1 byte thanks to MarcMush

x->y->count(r"^((.)(?*.*
(\3?+.*\2)))*
",x*'
'y)>0

Attempt This Online!

Yep, Julia string literals can contain an unescaped raw newline!

Beats Simeon Schaub's answer by 2 bytes when both are converted to the same type of declaration, e.g. currying, as used here.

Of course, both could also be 2 bytes shorter with operator overloading.

\$\endgroup\$
3
  • \$\begingroup\$ @MarcMush Thanks. BTW, I can't help but feel that you disapprove of my presenting the curried function as the answer, rather than the operator-overloading one. My logic is this: there's only one operator available for this type of overload (and even if there were more than one, it'd still be very limited number). A function is supposed to be usable by any program, even a large one. If the presented golfed function can be the only one used by any given program, its being a function is a sham – it's really just a full program masquerading as a function. \$\endgroup\$
    – Deadcode
    Aug 16, 2022 at 14:44
  • \$\begingroup\$ It's commonly accepted (I'm too lazy to find on meta but I'm pretty sure it is) and you can use $ than is unused by default \$\endgroup\$
    – MarcMush
    Aug 20, 2022 at 8:26
  • \$\begingroup\$ And it returns a function, without changing the original function Try it online! \$\endgroup\$
    – MarcMush
    Aug 20, 2022 at 8:34
1
\$\begingroup\$

CoffeeScript 73

Here's an alternative CoffeeScript answer, using regexes instead of recursion:

z=(x,y)->a='.*';a+=c+'.*'for c in x;b=eval('/'+a+'/');(y.replace b,'')<y

If the haystack matches a very greedy regex constructed from the needle, it will be replaced with an empty string. If the haystack is shorter than it started, the needle was a subsequence.

Returns false when x and y are both empty strings. Think we need a philosopher to tell us if an empty string is a subsequence of itself!

(Posted as a separate answer from my previous because it feels different enough to justify it).

\$\endgroup\$
1
\$\begingroup\$

PowerShell, 38

$args[1]-clike($args[0]-replace'','*')

Of course, any such regex- or pattern-matching-based solution has severe performance problems with longer strings. But since shortness is the criterion ...

\$\endgroup\$
1
\$\begingroup\$

A sort of anti-solution generating all subsequences of Y:

Python 93

l=len(y)
print x in[''.join(c for i,c in zip(bin(n)[2:].rjust(l,'0'),y)if i=='1')for n in range(2**l)]
\$\endgroup\$
1
\$\begingroup\$

APL (31)

String handling is a bit lacking in APL.

{(⊂'')∊N←⍵↓⍨¨1,⍨=/⊃¨⍵:~×⍴⊃N⋄∇N}

usage:

      {(⊂'')∊N←⍵↓⍨¨1,⍨=/⊃¨⍵:~×⍴⊃N⋄∇N} 'anna' 'banana'
1
      {(⊂'')∊N←⍵↓⍨¨1,⍨=/⊃¨⍵:~×⍴⊃N⋄∇N} 'Anna' 'banana'
0
      {(⊂'')∊N←⍵↓⍨¨1,⍨=/⊃¨⍵:~×⍴⊃N⋄∇N} '' 'banana'
1
\$\endgroup\$
1
\$\begingroup\$

Python 132

Similar to Daniero's. Not the easiest solution, but it was fun to try. I'm new to Python, so I'm sure I could make it shorter if I knew a little bit more.

def f(i):
    s=x;j=0
    while j<len(s):t=~i%2;s=[s[:j]+s[j+1:],s][t];j+=t;i>>=1
    return s==y
print True in map(f,range(1,2**len(x)))
\$\endgroup\$
1
\$\begingroup\$

Python - 72

def f(a,b):
 c=len(a)
 for i in b:a=a.replace(i,"",1)
 print len(a+b)==c
\$\endgroup\$
0
1
\$\begingroup\$

Retina, 26 bytes (not competing)

The language is newer than the challenge. Byte count assumes ISO 8859-1 encoding. Input is taken on two lines with Y first.

+`^(.)(.*¶)(?(\1).|)
$2
¶$

Try it online

\$\endgroup\$
1
\$\begingroup\$

Python (75 52)

s=lambda a,b:a==''or b>''and s(a[a[0]==b[0]:],b[1:])

Simple recursive solution. First time golfing, so any tips on whittling this down are much appreciated :)

Tested with the following:

assert s('anna', 'banana') == True
assert s('oo0', 'oFopp0') == True
assert s 'this', 'this is a string') == True
assert s('that', 'this hat is large') == True
assert s('cba', 'abcdefg') == False

Thanks to @lirtosiast for some clever boolean tricks.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ You can get this down to 52 characters: s=lambda a,b:a==''or b>''and s(a[a[0]==b[0]:],b[1:]) \$\endgroup\$
    – lirtosiast
    Mar 10, 2016 at 1:18
  • \$\begingroup\$ Thanks, that's clever, using the boolean as the 0/1 index into the splice :) \$\endgroup\$
    – foslock
    Mar 10, 2016 at 2:13
1
\$\begingroup\$

PHP, 75 65 64 bytes

for(;$p=@strpos(_.$argv[2],$c=$argv[1][$i++],$p+1););echo""==$c;

takes input from command line arguments; prints 1 for true, empty string for false. Run with -r.

explanation:

  • strpos returns false if needle $c is not in the haystack $argv[2] (after position $p),
    causing the loop to break.
  • strpos also returns false for an empty needle, breaking the loop at the end of $argv[1].
  • If $argv[1] is a subsequence of $argv[2], $c will be empty when the loop breaks.
  • strpos needs @ to suppress Empty needle warning.
\$\endgroup\$
2
  • \$\begingroup\$ +$p instead of $p+1 after that ther is no need for the underscore \$\endgroup\$ Mar 14, 2017 at 17:47
  • \$\begingroup\$ @JörgHülsermann +1 is needed to advance in the haystack string; and the underscore avoids $p=-1 initialization. But ... I can avoid false!==. \$\endgroup\$
    – Titus
    Mar 14, 2017 at 17:50
1
\$\begingroup\$

Swift, 27

print(Y.range(of:X) != nil)
\$\endgroup\$
0
1
\$\begingroup\$

APL (Dyalog Unicode), 18 bytesSBCS

Full program. Prompts for Y then for X.

×≢(∊'.*'∘,¨⍞)⎕S⍬⊢⍞

Try it online!

 prompt (for Y)

 yield that (separates from it)

()⎕S⍬ search for occurrences of the following, yielding one empty list for each match:

 prompt (for X)

'.*'∘,¨ prepend .* to each character

ϵnlist (flatten)

 tally the number of matches

× sign of that

\$\endgroup\$
1
\$\begingroup\$

APL(NARS), chars 46, bytes 92

{(⊂,⍺)∊(⊂''),↑¨,/¨{⍵⊂w}¨{⍵⊤⍨k⍴2}¨⍳¯1+2*k←≢w←⍵}

test:

  h←{(⊂,⍺)∊(⊂''),↑¨,/¨{⍵⊂w}¨{⍵⊤⍨k⍴2}¨⍳¯1+2*k←≢w←⍵}
  '' h 'z00'
1
  'z00' h 'z00'
1
  'z00' h '00z0'
0
  'aa' h 'anna'
1
  'anna' h 'banana'
1
  'Anna' h 'banana'
0

comment:

{(⊂,⍺)∊(⊂''),↑¨,/¨{⍵⊂w}¨{⍵⊤⍨k⍴2}¨⍳¯1+2*k←≢w←⍵}
 ⍳¯1+2*k←≢w←⍵    this assign to w the argument and k argument lenght, it return 1..(2^k)-1 range
 {⍵⊤⍨k⍴2}¨      for each element of 1..(2^k)-1 convert in base 2 with lenght k (as the arg lenght)
 {⍵⊂w}¨         use the binary array above calculation for all partition argument
 ,/¨            concatenate each element of partition
 ↑¨             get the firs element of each element because they are all enclosed
 (⊂''),         add to the array the element (⊂'')
 (⊂,⍺)∊         see if (⊂,⍺) is one element of the array, and return 1 true o 0 false

How all you can see the comments are +- superfluous all is easy...

I have to say not understand why the last instruction is not "(,⍺)∊" in the place of "(⊂,⍺)∊" because for example in code

  q←{↑¨,/¨{⍵⊂w}¨{⍵⊤⍨k⍴2}¨⍳¯1+2*k←≢w←⍵}
  o q '123'
┌7──────────────────────────────────────┐
│┌1─┐ ┌1─┐ ┌2──┐ ┌1─┐ ┌2──┐ ┌2──┐ ┌3───┐│
││ 3│ │ 2│ │ 23│ │ 1│ │ 13│ │ 12│ │ 123││
│└──┘ └──┘ └───┘ └──┘ └───┘ └───┘ └────┘2
└∊──────────────────────────────────────┘
  o (,'3')
┌1─┐
│ 3│
└──┘

all you see array of 1 element (,'3') is the element of the set of instruction q '123', but

  o (,'3')∊q '123'
┌1─┐
│ 0│
└~─┘

return one array of unclosed 0 instead of number 1... for workaround that one has to write:

  o (⊂,'3')∊q '123'
1
~

that is the right result even if the element seems different because :

  o (⊂,'3')
┌────┐
│┌1─┐│
││ 3││
│└──┘2
└∊───┘

It is sure i make some error because i am not so smart... where is my error?

\$\endgroup\$
1
\$\begingroup\$

Julia 1.0, 53 bytes

f(x,y)=(x==""||[x=x[2:end] for c=y if c==x[1]];x=="")

Try it online!

\$\endgroup\$
1
1
\$\begingroup\$

JavaScript, 32 bytes

Repost of a port of Kevin's Java solution to a duplicate challenge, modified in case my choices for I/O weren't standards at the time this challenge was posted.

x=>y=>!!y.match([...x].join`.*`)

Try it online! (will update with this challenge's test cases when I get back to a computer)

\$\endgroup\$
1
\$\begingroup\$

Perl 6, 34 28 bytes

-6 bytes thanks to nwellnhof

{$!=S:g/<(/.*/;&{?/<{$!}>/}}

Try it online!

Anonymous code block that takes input curried, like f(X)(Y). This does the familiar join by .* and evaluate as a regex as other answers, but takes a couple of shortcuts.

Explanation:

{                          }  # Anonymous code block
 $!=            # Assign to $!
    S:g/<(/.*/  # Inserting .* between every character
              ;&{         }   # And return an anonymous code block
                 ?/      /    # That returns if the input matches
                   <{$!}>     # The $! regex
\$\endgroup\$
0
1
\$\begingroup\$

Jelly, 3 bytes

ŒPi

Try it online!

Outputs 0 for false and a non-negative integer for true

How it works

ŒPi - Main link. Takes X on the left and Y on the right
ŒP  - Powerset of X
  i - Index of y, or 0
\$\endgroup\$
1
\$\begingroup\$

Husk, 2 bytes

€Ṗ

Try it online!

Having a single byte builtin for powerset is useful.

\$\endgroup\$
1
\$\begingroup\$

Java 8, 163 162 38 35 bytes

a->b->b.matches(a.replace("",".*"))

-124 bytes by converting to Java 8, and pasting my answer from the duplicated challenge.

NOTE: Doesn't work if the input contains special regex-characters, but this would invalidate a lot of existing answers as well.

Try it online.

Explanation:

a->b->         // Method with two String parameters and boolean return-type
  b.matches(   //  Check if the second input matches the regex:
   a           //   The first input,
    .replace("",".*"))
               //   where every character is surrounded with ".*"

For example:

a="anna"
b="banana"

Will do the check:

"banana".matches("^.*a.*n.*n.*a.*$")
\$\endgroup\$
5
  • 1
    \$\begingroup\$ You're mishandling special regexp characters like "." though \$\endgroup\$ Jan 26, 2021 at 18:02
  • \$\begingroup\$ @StefanReich You're right, but the same applies to almost any other existing answer, though. But I've added a note to mention this in the answer (and golfed it by 3 bytes at the same time). \$\endgroup\$ Jan 26, 2021 at 19:44
  • \$\begingroup\$ Come on... you're saying there is a bug in THIS? >> à øV << (the Japt program, whatever that is) \$\endgroup\$ Jan 26, 2021 at 21:53
  • \$\begingroup\$ @StefanReich The golfing languages like Jelly, Japt, 05AB1E, etc. are probably fine, since most of them just use the powerset and check if the second input is in it. I was referring to the answers using regex like mine, like the accepted Perl answer; the Python answer of Eric; the Ruby answer; etc. All answers that use regex are similar as mine (add a ".*" after each characters, and check if it matches the second input) are most likely invalid if the inputs contain special regex characters. \$\endgroup\$ Jan 26, 2021 at 22:07
  • \$\begingroup\$ I was just messing around :) \$\endgroup\$ Jan 26, 2021 at 22:43
1
\$\begingroup\$

MMIX, 40 bytes (10 instrs)

C strings.

00000000: 8302 0000 8303 0100 dc04 0203 30FF 0203  ............0...
00000010: 73FF FF01 2200 00FF 2301 0101 5b04 fff9  s..."...#...[...
00000020: 7300 0201 f801 0000                      s.......

Disassembly

subseq  LDBU $2,$0,0        // loop: av = *a
        LDBU $3,$1,0        // bv = *v
        MOR  $4,$2,$3       // t0 = av && bv (MOR is faster than MUL)
        CMP  $255,$2,$3     // t1 = av <=> bv
        ZSZ  $255,$255,1    // t1 = !t1
        ADDU $0,$0,$255     // a += t1
        ADDU $1,$1,1        // b += 1
        PBNZ $4,subseq      // iflikely(t0) goto loop
        ZSZ  $0,$2,1        // a = !t0
        POP  1,0            // return a

Obvious algorithm, with only one branch!

For wchar_t, replace LDBU with LDWU (and similarly for codepoint_t); additionally, replace ADDU $0,$0,$255 with 2ADDU $0,$255,$0 (4ADDU for codepoints), and ADDU $1,$1,1 with ADDU $1,$1,2 or ADDU $1,$1,4.

\$\endgroup\$
1
\$\begingroup\$

Vyxal, 2 bytes

ṗc

Try it Online!

\$\endgroup\$
1
\$\begingroup\$

K (ngn/k), 32 18 bytes

~#*{(=/*'x;1)_'x}/

Try it online!

\$\endgroup\$
1
\$\begingroup\$

Thunno 2 G, 2 bytes

ʠ=

Attempt This Online!

Port of Kevin Cruijssen's 05AB1E answer.

Explanation

ʠ=  # Implicit input
ʠ   # Powerset of the first input string
 =  # Vectorised equality check with the second input string
    # Check if any are true, and implicitly output
\$\endgroup\$
1
\$\begingroup\$

Nekomata + -e, 2 bytes

S=

Attempt This Online!

S       Check if any subset of the first string
 =      is equal to the second string
\$\endgroup\$
0
\$\begingroup\$

C, 120

main(i,c){char x[99],y[99];c=0;gets(y),gets(x);for(i=0;y[i]!='\0';)c+=y[i++]==x[c]?1:0;puts(x[c]=='\0'?"True":"False");}
\$\endgroup\$
1
  • \$\begingroup\$ You can save at least 15 chars by moving c=0 to the loop initialiser and eliminating every instance of == in favour of "non-zero is truthy" conditions. \$\endgroup\$ Apr 16, 2012 at 16:36
0
\$\begingroup\$

Javascript, 104 chars

function _(x,y){f=true;for(c in x){if(y.indexOf(x[c])>-1)y=y.replace(x[c],"");else{f=!f;break}}return f}

Ungolfed

function _(x,y){
f=true;
    for(c in x)
    {
        if(y.indexOf(x[c])>-1)
           y=y.replace(x[c],"");
        else {
            f=!f;
            break;
        }
    }
    return f;
}
\$\endgroup\$
5
  • \$\begingroup\$ This appears to test whether x is a substring of y, but it's supposed to test whether x is a subsequence of y. E.g., 'anna' is a subsequence of 'banana', but 'banana'.indexOf('anna')>-1 evaluates to false. \$\endgroup\$
    – r.e.s.
    Sep 19, 2012 at 4:14
  • \$\begingroup\$ @r.e.s. : My bad dint read the question properly. Thanks \$\endgroup\$
    – Clyde Lobo
    Sep 19, 2012 at 8:57
  • \$\begingroup\$ @r.e.s. posted a altogether new answer \$\endgroup\$
    – Clyde Lobo
    Sep 19, 2012 at 9:17
  • \$\begingroup\$ What does the new answer do for _("ab", "ba")? \$\endgroup\$ Sep 19, 2012 at 13:19
  • \$\begingroup\$ returns true. demo jsfiddle.net/yvAdT \$\endgroup\$
    – Clyde Lobo
    Sep 19, 2012 at 18:28
0
\$\begingroup\$

J (20 chars)

(<x)e.(#:i.2^#y)<@#y

The input is given in the variables x and y. It makes a list of all subsequences of y, so don't use it for very big strings.

\$\endgroup\$
0
\$\begingroup\$

Python (72)

import itertools as I;any(tuple(X)==Z for Z in I.permutations(Y,len(X)))
\$\endgroup\$
1
  • 1
    \$\begingroup\$ No, that use of permutations ignores the required order of the elements; e.g., X='z00' and Y='00z0' should output False (whereas your program outputs True). \$\endgroup\$
    – r.e.s.
    Mar 17, 2014 at 22:42
0
\$\begingroup\$

JavaScript (ES6), 42 bytes

Takes input n (needle) and h (haystack) in currying syntax (n)(h).

n=>h=>!!RegExp(n.split``.join`.*`).exec(h)

Test

let f =

n=>h=>!!RegExp(n.split``.join`.*`).exec(h)

console.log(f(''    )('z00'   )); // true
console.log(f('z00' )('z00'   )); // true 
console.log(f('z00' )('00z0'  )); // false
console.log(f('aa'  )('anna'  )); // true
console.log(f('anna')('banana')); // true
console.log(f('Anna')('banana')); // false

\$\endgroup\$
3
  • \$\begingroup\$ What if n contains regex special characters? \$\endgroup\$
    – Titus
    Mar 14, 2017 at 16:11
  • \$\begingroup\$ @Titus Well, I assumed n is in [A-Za-z0-9] since the challenge mentions that both input strings are alphanumeric. \$\endgroup\$
    – Arnauld
    Mar 14, 2017 at 16:16
  • \$\begingroup\$ woops missed that. :) \$\endgroup\$
    – Titus
    Mar 14, 2017 at 16:36
0
\$\begingroup\$

REXX, 76 bytes

o=1
do while x>''
  parse var x a+1 x
  parse var y(a)b+1 y
  o=o&a=b
  end
return o

Note that x and y are consumed by this routine. Readability is impaired by skipping a lot of whitespace and parentheses.

\$\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.