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

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

Haskell, 36 bytes

(a:b)%(c:d)=([a|a/=c]++b)%d
s%t=s<=t

Try it online!


37 bytes

(.map concat.mapM(\c->["",[c]])).elem

Try it online!

I think mapM postdates this challenge. If we can assume the characters are printable, we can do

36 bytes

(.map(filter(>' ')).mapM(:" ")).elem

Try it online!


37 bytes

(null.).foldr(?)
c?(h:t)|c==h=t
c?s=s

Try it online!

\$\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
\$\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\$
  • \$\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\$ – Peter Taylor Apr 16 '12 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\$
  • \$\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 '12 at 4:14
  • \$\begingroup\$ @r.e.s. : My bad dint read the question properly. Thanks \$\endgroup\$ – Clyde Lobo Sep 19 '12 at 8:57
  • \$\begingroup\$ @r.e.s. posted a altogether new answer \$\endgroup\$ – Clyde Lobo Sep 19 '12 at 9:17
  • \$\begingroup\$ What does the new answer do for _("ab", "ba")? \$\endgroup\$ – Peter Taylor Sep 19 '12 at 13:19
  • \$\begingroup\$ returns true. demo jsfiddle.net/yvAdT \$\endgroup\$ – Clyde Lobo Sep 19 '12 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
    \$\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 '14 at 22:42
0
\$\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\$
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\$
  • \$\begingroup\$ What if n contains regex special characters? \$\endgroup\$ – Titus Mar 14 '17 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 '17 at 16:16
  • \$\begingroup\$ woops missed that. :) \$\endgroup\$ – Titus Mar 14 '17 at 16:36
0
\$\begingroup\$

Pyth, 5 bytes (non-competing)

}hQye

Explanation

}hQye
 hQ       The first input...
}         ... is an element of...
   y      ... the power set...
    eQ    ... of the second input.
\$\endgroup\$
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\$
0
\$\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\$
0
\$\begingroup\$

Python 2, 47 bytes

x,y=map(list,input())
while x:y.remove(x.pop())

Try it online!

Takes two quote-delimited strings via STDIN as input.

Output is by presence or absence of an error, which is allowed per meta consensus.

Explanation:

             # get arguments from STDIN
             input()
    # convert each argument to a list
    map(list,.......)
# split arguments into two variables
x,y=..................

# while x still has elements
while x:
                 # remove the final element of x and return its value
                 x.pop()
        # remove the first matching item in y
        # this will error if there is no matching element
        y.remove(.......)

# if the loop is exited without error, all elements in x were in y
\$\endgroup\$
  • \$\begingroup\$ This doesn't look like it checks that the removed letters are in the right order. \$\endgroup\$ – xnor Feb 22 at 17:16
0
\$\begingroup\$

x86-16 Assembly, 11 bytes

Binary:

00000000: 41ac f2ae e303 4a75 f83b ca              A.....Ju.;.

Unassembled listing:

41          INC  CX                 ; Loop counter is 1 greater than string length 
        SCAN_LOOP: 
AC          LODSB                   ; load next char of acronym into AL 
F2/ AE      REPNZ SCASB             ; search until char AL is found 
E3 03       JCXZ DONE               ; stop if end of first string reached 
4A          DEC  DX                 ; decrement second string counter 
75 F8       JNZ  SCAN_LOOP          ; stop if end of second string reached 
        DONE: 
3B CA       CMP  CX, DX             ; which string ended first?

Input: Y string pointer in SI, length in CX. X string pointer in DI, length in DX. Output is Falsey if CF.

Example test program:

This test program uses additional PC DOS API I/O routines to take multi-line input from STDIN.

enter image description here

Download and test ACRON.COM.

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

Japt, 4 bytes

Repost from a duplicate challenge.

Takes input in reverse order (Y, then X).

à øV

Try it

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

Red, 82 bytes

func[x y][parse/case y collect[foreach c x[keep reduce['to c 'skip]]keep[to end]]]

Try it online!

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

Charcoal, 18 bytes

Fη≔✂θ⁼ι∧θ§θ⁰Lθ¹θ¬θ

Try it online! Link is to verbose version of code. Language postdates challenge. Uses Charcoal's default Boolean output of - for true, nothing for false. Explanation:

Fη

Loop over the characters of Y.

⁼ι∧θ§θ⁰

See if this character is the next character of X.

≔✂θ...Lθ¹θ

If so then remove that character from X.

¬θ

Were all the characters of X consumed?

\$\endgroup\$
0
\$\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\$
0
\$\begingroup\$

Java 8, 163 162 38 bytes

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

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

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,
    .replaceAll("",".*"))
               //   where every character is surrounded with ".*"

For example:

a="anna"
b="banana"

Will do the check:

"banana".matches("^.*a.*n.*n.*a.*$")
\$\endgroup\$
0
\$\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\$

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.