23
\$\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\$
  • 1
    \$\begingroup\$ Why is 'anna' substr of 'banana'? \$\endgroup\$ – kaoD Apr 26 '12 at 5:04
  • 4
    \$\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 '12 at 13:33
  • 2
    \$\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 '12 at 14:50

50 Answers 50

18
\$\begingroup\$

Perl 5, 17 bytes (+1?), full program

s//.*/g;$_=<>=~$_

Try it online!

Invoke with the p flag to the perl interpreter, as in perl -pe 's//.*/g;$_=<>=~$_'. Per the established scoring rules when this challenge was originally posted, this flag costs one extra byte. Under more recent rules, AFAICT, it may be free.

Either way, the input strings should be supplied on separate newline-terminated lines on stdin. Output (to stdout) will be 1 if the first input string is a substring of the second, or nothing at all if it's not.

Note that both input lines must have a newline at the end, or the program won't work correctly. Alternatively, you can add the l command line flag to the invocation to make perl strip the newlines; depending on the scoring rules in effect, this may or may not cost one extra byte. Note that using this flag will also append a newline to the output.

Original version (snippet, 18 bytes / chars)

$x=~s//.*/g,$y=~$x

Input is given in the variables $x and $y, result is the value of the expression (in scalar context). Note that $x is modified in the process. (Yes, I know using $_ instead of $x would let me save four chars, but doing that in a snippet that feels a bit too cheesy for me.)

How does it work?

The first part, $x=~s//.*/g, inserts the string .* between each character in $x. The second part, $y=~$x, treats $x as a regexp and matches $y against it. In Perl regexps, .* matches zero or more arbitrary characters, while all alphanumeric characters conveniently match themselves.

\$\endgroup\$
  • \$\begingroup\$ According to out (new?) consensus, submissions must be program or function, not snippet. If your submission doesn't satisfy that, consider editing it. \$\endgroup\$ – user202729 Mar 26 '18 at 6:21
  • \$\begingroup\$ @user202729: This challenge is a lot older than that consensus, so unless it's assumed to apply retroactively, the answers in this thread should probably be "grandfathered" in. That said, I did just add a version that complies with current rules, and may even be one byte / char shorter (note that byte-based counting is also newer than this challenge, AFAIK) depending on how you count command-line switches. \$\endgroup\$ – Ilmari Karonen Mar 26 '18 at 9:06
9
\$\begingroup\$

Ruby, 32 characters

s=->x,y{y=~/#{[*x.chars]*".*"}/}

This solution returns nil if x isn't a subsequence of y and a number otherwise (i.e. ruby equivalents to false and true). Examples:

p s['','z00']        # => 0   (i.e. true)
p s['z00','z00']     # => 0   (i.e. true)
p s['z00','00z0']    # => nil (i.e. false)
p s['anna','banana'] # => 1   (i.e. true)
p s['Anna','banana'] # => nil (i.e. false)
\$\endgroup\$
  • 1
    \$\begingroup\$ i did basically the same thing, but it's too similar so i won't post it. i think it is acceptable to leave off the lambda, which would leave you with y=~/#{[*x.chars]*".*"}/ (23 chars). cheers! \$\endgroup\$ – Patrick Oscity Apr 26 '12 at 12:46
  • 1
    \$\begingroup\$ or even y=~/#{x.split("")*".*"}/ (21 chars) :) \$\endgroup\$ – Patrick Oscity Apr 26 '12 at 12:53
  • \$\begingroup\$ @padde The split one is actually 24 chars. \$\endgroup\$ – Howard Apr 27 '12 at 0:23
  • 1
    \$\begingroup\$ sorry, i guess i accidentally left off the y=~ while fiddling with this in irb... \$\endgroup\$ – Patrick Oscity Apr 27 '12 at 13:27
  • \$\begingroup\$ My version is 2 char shorter. \$\endgroup\$ – Hauleth Sep 12 '12 at 9:47
7
\$\begingroup\$

Haskell, 51 37

h@(f:l)%(g:m)=f==g&&l%m||h%m;x%y=x<=y

Thanks to Hammar for the substantial improvement. It's now an infix function, but there seems to be no reason why it shouldn't.

Demonstration:

GHCi> :{
GHCi| zipWith (%) [""   , "z00", "z00" , "anna"  , "Anna"]
GHCi|             ["z00", "z00", "00z0", "banana", "banana"]
GHCi| :}
[True,True,False,True,False]
\$\endgroup\$
  • \$\begingroup\$ Since the empty list is smaller than any other list, you can simplify the base cases to s x y=x<=y. Also, you can save a few more by making it an operator and using an @-pattern instead of (f:l). This cuts it down to 37 characters: h@(f:l)%(g:m)=f==g&&l%m||h%m;x%y=x<=y \$\endgroup\$ – hammar Apr 18 '12 at 6:38
6
\$\begingroup\$

Python (48 chars)

import re;s=lambda x,y:re.search('.*'.join(x),y)

Same approach as Howard's Ruby answer. Too bad about Python's need to import the regex package and its "verbose" lambda. :-)

\$\endgroup\$
  • 1
    \$\begingroup\$ I agree, lambda is verbose. \$\endgroup\$ – CalculatorFeline Mar 9 '16 at 19:31
4
\$\begingroup\$

Python, 59 characters

def s(x,y):
 for c in y:
  if x:x=x[c==x[0]:]
 return x==""

I figured my answer would be better expressed in Python.

Edit: Added r.e.s.'s suggestions.

\$\endgroup\$
  • \$\begingroup\$ Surely given x="a" and y="ab" you would exit the loop with y=="b" and return false? \$\endgroup\$ – Peter Taylor Apr 15 '12 at 22:29
  • \$\begingroup\$ @PeterTaylor Yeah, I noticed when I was running the examples as tests after posting that I've mixed x and y up. In my functions y needs to be a subsequence of x. I think I'd better change them to avoid any confusion. \$\endgroup\$ – Gareth Apr 15 '12 at 22:31
  • \$\begingroup\$ You can get this down to 59 chars: def s(x,y): for c in y: if x:x=x[c==x[0]:] return x=="". It doesn't display correctly in a comment, but I think you can see what I mean. (Also, one added space is enough to increase the indent level.) \$\endgroup\$ – r.e.s. Apr 15 '12 at 23:20
  • \$\begingroup\$ @r.e.s. Thanks, Python's not a language I use much as you can probably tell. Nice golfing. (63 characters according to the Codegolf userscript - it must be counting the newlines). \$\endgroup\$ – Gareth Apr 15 '12 at 23:26
  • 1
    \$\begingroup\$ You can use extending slicing to protect against x being '' and save several chars by writing x=x[c==x[0:1]:] \$\endgroup\$ – Nolen Royalty Sep 10 '12 at 7:57
4
\$\begingroup\$

GolfScript (22 chars)

X[0]+Y{1$(@={\}*;}/0=!

Assumes that input is taken as two predefined variables X and Y, although that is rather unusual in GolfScript. Leaves 1 for true or 0 for false on the stack.

\$\endgroup\$
4
\$\begingroup\$

C (52 chars)

s(char*x,char*y){return!*x||*y&&s(*x-*y?x:x+1,y+1);}

Test cases

\$\endgroup\$
  • \$\begingroup\$ s(char*x,char*y){x=!*x||*y&&s(x+(*x==*y),y+1);} \$\endgroup\$ – l4m2 Mar 26 '18 at 17:11
4
\$\begingroup\$

Burlesque (6 chars)

6 chars in Burlesque: R@\/~[ (assuming x and y are on the stack. See here in action.)

\$\endgroup\$
4
\$\begingroup\$

C, 23:

while(*y)*x-*y++?0:x++;

result in *x

http://ideone.com/BpITZ

\$\endgroup\$
3
\$\begingroup\$

PHP, 90 characters

<?function s($x,$y){while($a<strlen($y))if($y[$a++]==$x[0])$x=substr($x,1);return $x=="";}
\$\endgroup\$
  • \$\begingroup\$ You can remove the if statement and simplify to $x=substr($x,$y[$a++]==$x[0]): ideone.com/Ch9vK \$\endgroup\$ – mellamokb Apr 16 '12 at 22:08
  • \$\begingroup\$ Also here is a slightly shorter 82-character solution using recursion: ideone.com/IeBns \$\endgroup\$ – mellamokb Apr 16 '12 at 22:19
3
\$\begingroup\$

Scala 106:

def m(a:String,b:String):Boolean=(a.size==0)||((b.size!=0)&&((a(0)==b(0)&&m(a.tail,b.tail))||m(a,b.tail)))
\$\endgroup\$
3
\$\begingroup\$

CoffeeScript 112 100 95 89

My first attempt at code golf... hope I don't shame my family!

z=(x,y)->a=x.length;return 1if!a;b=y.indexOf x[0];return 0if!++b;z x[1..a],y[b..y.length]

Edit: turns out Coffeescript is more forgiving than I thought with whitespace.

Thanks to r.e.s. and Peter Taylor for some tips for making it a bit sleeker

\$\endgroup\$
  • \$\begingroup\$ A few more chars can be eliminated as follows (this won't display right in a comment, but I think you can see what I mean): z=(x,y)-> a=x.length return 1if a==0 b=y.indexOf x[0] return 0if b<0 z x[1..a],y[b+1..y.length]. (In some browsers, e.g. Chrome, you can see comment code properly displayed by right-clicking, then Inspect Element.) \$\endgroup\$ – r.e.s. Apr 23 '12 at 17:33
  • \$\begingroup\$ a.length is never going to be negative, so you can save one character more by replacing if a==0 with if a<1. I don't know how CoffeeScript's tokenisation works, but if it lexes if0 as two tokens you could save two more by reversing both conditions (i.e. if1>a). \$\endgroup\$ – Peter Taylor Apr 23 '12 at 21:42
  • \$\begingroup\$ Good points. if1>a isn't valid, but if!a is and is a character shorter! I also realised that I could shave an extra character converting b+1 to b and incrementing it on the previous line, also making the same if trick possible since it was dealing with a 0/non-0 situation. \$\endgroup\$ – Johno Apr 24 '12 at 9:59
3
\$\begingroup\$

C #, 70 113 107 90 characters

static bool S(string x,string y){return y.Any(c=>x==""||(x=x.Remove(0,c==x[0]?1:0))=="");}
\$\endgroup\$
  • 6
    \$\begingroup\$ Doesn't this search for a substring rather than a subsequence? \$\endgroup\$ – Gareth Apr 15 '12 at 23:17
  • \$\begingroup\$ yes, I misread. Should be fixed now. \$\endgroup\$ – mizer Apr 18 '12 at 1:41
  • 1
    \$\begingroup\$ As fun as Linq is, I think you can save 10% by using recursion instead. \$\endgroup\$ – Peter Taylor Apr 18 '12 at 8:13
  • \$\begingroup\$ Here's my best attempt. Still longer. static bool S(string x,string y){if(x!=""&&y=="")return false;return x==""||S(y[0]==x[0]?x.Remove(0,1):x,y.Remove(0,1));} \$\endgroup\$ – mizer Apr 26 '12 at 2:15
  • \$\begingroup\$ You can reduce the recursive one to x==""||y!=""&&S(...), but it's still longer than the updated Linq version. Nice use of Any! \$\endgroup\$ – Peter Taylor Apr 26 '12 at 8:05
3
\$\begingroup\$

Mathematica 19 17 27

LongestCommonSequence returns the longest non-contiguous subsequence of two strings. (Not to be confused with LongestCommonSubsequence, which returns the longest contiguous subsequence.

The following checks whether the longest contiguous subsequence is the first of the two strings. (So you must enter the shorter string followed by the larger string.)

LongestCommonSequence@##==#& 

Examples

LongestCommonSequence@## == # &["", "z00"]
LongestCommonSequence@## == # &["z00", "z00"]
LongestCommonSequence@## == # &["anna", "banana"]
LongestCommonSequence@## == # &["Anna", "banana"]

True True True False

The critical test is the third one, because "anna" is contained non contiguously in "banana".

\$\endgroup\$
3
\$\begingroup\$

Python 3.8 (pre-release), 42 bytes

lambda a,b:''in[a:=a[a[:1]==c:]for c in b]

Try it online!

Python 3.8 (pre-release), 48 bytes

lambda a,b,j=0:all((j:=1+b.find(c,j))for c in a)

Try it online!

Python 2, 48 bytes

lambda a,b:re.search('.*'.join(a),b)>0
import re

Try it online!

Copied from this answer of Lynn. The >0 can be omitted if just truthy/falsey output is OK.

Python 2, 50 bytes

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

Try it online!

Python 2, 50 bytes

lambda a,b:reduce(lambda s,c:s[c==s[:1]:],b,a)==''

Try it online!

\$\endgroup\$
  • \$\begingroup\$ Great use of the walrus. \$\endgroup\$ – Jonathan Allan Aug 20 at 18:03
2
\$\begingroup\$

C - 74 71 64

This doesn't beat Peter Taylor's solution, but I think it's pretty fun (plus, this is a complete working program, not just a function)

main(int c,char**v){for(;*v[1]!=0;++v[1])v[2]+=*v[1]==*v[2];return*v[2];}

main(int c,char**v){for(;*v[1];++v[1])v[2]+=*v[1]==*v[2];return*v[2];}


main(c,v)char**v;{while(*v[1])v[2]+=*v[1]++==*v[2];return*v[2];}

And ungolfed:

main(int argc, char** argv){
   char * input = argv[1];
   char * test  = argv[2];

   // advance through the input string. Each time the current input
   // character is equal to the current test character, increment
   // the position in the test string.

   for(; *input!='\0'; ++input) test += *input == *test;

   // return the character that we got to in the test string.
   // if it is '\0' then we got to the end of the test string which
   // means that it is a subsequence, and the 0 (EXIT_SUCCESS) value is returned
   // otherwise something non-zero is returned, indicating failure.
   return *test;
}

To test it you can do something like:

./is_subsequence banana anna && echo "yes" || echo "nope"    
# yes
./is_subsequence banana foobar && echo "yes" || echo "nope"    
# nope
\$\endgroup\$
  • \$\begingroup\$ !=0 in a condition is a bit verbose... Program vs function is something which the question needs to specify clearly, and here it doesn't, so the answers take different options. \$\endgroup\$ – Peter Taylor Apr 24 '12 at 13:32
  • \$\begingroup\$ Damn, that !='\0' is a bad (good?) habit from writing non-golf code, I've let that slip into my last two rounds of golf, I'll have to be more careful in the future. As to program vs. function, yes, you're absolutely right. \$\endgroup\$ – Gordon Bailey Apr 24 '12 at 17:55
  • \$\begingroup\$ @GordonBailey sorry for the bump, but I made a few changes into a shorter version. \$\endgroup\$ – oldrinb Sep 9 '12 at 14:54
2
\$\begingroup\$

Python, 66 62 59 58 chars

Kind of a fun solution, definitely a neat problem.

def f(n,h,r=0):
 for c in h:r+=n[r:r+1]==c
 return r==len(n)
\$\endgroup\$
2
\$\begingroup\$

Ruby 32 30 28

f=->a,b{b.match a.tr'','.*'}

This will return MatchData instance if a is subsequence of b or nil otherwise.

Old version that find substring instead of subsequence

Ruby 15

f=->a,b{!!b[a]}

Using String#[](str) method that returns str if str is a substring of self and !! to return Boolean if returned value can be usable as boolean (and don't need to be true or false) then it can be only 13 chars:

f=->a,b{b[a]}

It will return nil if a is not a substring of b.

\$\endgroup\$
  • 2
    \$\begingroup\$ Nice, but the question asks for a subsequence rather than a substring. \$\endgroup\$ – Gareth Apr 19 '12 at 7:12
2
\$\begingroup\$

SWI-Prolog, SICStus

The built-in predicate sublist/2 of SICStus checks whether all the items in the first list also appear in the second list. This predicate is also available in SWI-Prolog via compatibility library, which can be loaded by the query [library(dialect/sicstus/lists)]..

Sample run:

25 ?- sublist("","z00").
true.

26 ?- sublist("z00","z00").
true .

27 ?- sublist("z00","00z0").
false.

28 ?- sublist("aa","anna").
true .

29 ?- sublist("anna","banana").
true .

30 ?- sublist("Anna","banana").
false.

The byte count can technically be 0, since all we are doing here is querying, much like how we run a program and supply input to it.

\$\endgroup\$
2
\$\begingroup\$

PHP, 41 Bytes

prints 1 for true and nothing for false

<?=!levenshtein($argv[1],$argv[2],0,1,1);

If only insertions from word 1 to word 2 done the count is zero for true cases

levenshtein

Try it online!

PHP, 57 Bytes

prints 1 for true and 0 for false

Creates a Regex

<?=preg_match(_.chunk_split($argv[1],1,".*")._,$argv[2]);

Try it online!

\$\endgroup\$
  • 1
    \$\begingroup\$ -2 bytes: leading .* is unnecessary. -2 bytes: don´t assign $argv to $a. +24 bytes: needs array_map(preg_quote()) for special characters (use parentheses as delimiters to avoid second preg_quote parameter.) \$\endgroup\$ – Titus Mar 14 '17 at 15:28
  • 2
    \$\begingroup\$ @Titus the leading .* is necessary for the input of an empty string and for the input I must only handle a possibly-empty case-sensitive alphanumeric string. You are right with the quote if there are special characters. Thank you for counting the assign. Copy and paste by an earlier solution and not think about it \$\endgroup\$ – Jörg Hülsermann Mar 14 '17 at 15:42
  • 1
    \$\begingroup\$ preg_match will not complain about an empty regex as long as the delimiters are there. It will just match anything. But preg_quote is only +22 bytes, not +24: array_map(preg_quote,str_split(...)). \$\endgroup\$ – Titus Mar 14 '17 at 16:02
  • 1
    \$\begingroup\$ But then, input is guaranteed to be alphanumeric :) But you still don´t need the leading .*. \$\endgroup\$ – Titus Mar 14 '17 at 16:38
2
\$\begingroup\$

Brachylog, 2 bytes

⊆ᵈ

Try it online!

As with this answer, is a built-in predicate that declares a relationship between the input and output variables, and is a meta-predicate that modifies it to declare that same relationship between the first and second elements of the input variable instead (and unify the output variable with the second element but as this is a decision problem that doesn't end up mattering here). X⊆Y is an assertion that X is a subsequence of Y, therefore so is [X,Y]⊆ᵈ.

This predicate (which of course outputs through success or failure which prints true. or false. when it's run as a program) takes input as a list of two strings. If input is a bit more flexible...

Brachylog, 1 byte

Try it online!

Takes string X as the input variable and string Y as the output variable. Outputs through success or failure, as before. If run as a full program, X is supplied as the input and Y is supplied as the first command line argument.

\$\endgroup\$
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\$
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\$
  • 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 '16 at 1:18
  • \$\begingroup\$ Thanks, that's clever, using the boolean as the 0/1 index into the splice :) \$\endgroup\$ – foslock Mar 10 '16 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\$
  • \$\begingroup\$ +$p instead of $p+1 after that ther is no need for the underscore \$\endgroup\$ – Jörg Hülsermann Mar 14 '17 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 '17 at 17:50
1
\$\begingroup\$

Swift, 27

print(Y.range(of:X) != nil)
\$\endgroup\$
  • \$\begingroup\$ Welcome to PPCG! \$\endgroup\$ – Martin Ender May 19 '17 at 21:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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