Given a string s and an array/list l, determine whether or not s can be made with parts from l.

For example, if the string is "Hello, world!" and the list is [' world!', 'Hello,'], then the program/function should return a truthy value, because you can arrange the list to form the string. The following list would also return a truthy value: ['l', 'He', 'o, wor', 'd!']. Just imagine the 'l' filling in where it needs to in he string. So yes, you may repeat elements of the list to form the string. If it cannot form the string, it should return a falsy value. Standard methods of IO, standard loopholes apply.

Test cases:

Input (In the form of s, l)
Output (1 if possible, 0 if impossible)

"Hello, world!", ["l", "He", "o, wor", "d!"]

"la lal al ", ["la", " l", "al "]

"this is a string", ["this should return falsy"]

"thi is a string", ["this", "i i", " a", " string"]

"aaaaa", ["aa"]

"foo bar foobar", ["foo", "bar", " ", "spam"]

"ababab", ["a","ba","ab"]

"", ["The string can be constructed with nothing!"]
  • \$\begingroup\$ Does it matter if the array contains more strings than are needed to construct the main string? \$\endgroup\$
    – Shaggy
    Commented Apr 27, 2017 at 23:36
  • \$\begingroup\$ What should the return value be in those cases? \$\endgroup\$
    – Shaggy
    Commented Apr 27, 2017 at 23:38
  • \$\begingroup\$ @Shaggy Truthy. If there is extra, then the string can be constructed with all the non-extra parts. I will add a test case. \$\endgroup\$
    – sporkl
    Commented Apr 27, 2017 at 23:39
  • 3
    \$\begingroup\$ I recommend adding this test case: "ababab", ["a","ba","ab"] \$\endgroup\$ Commented Apr 27, 2017 at 23:51
  • 3
    \$\begingroup\$ I'd suggest you add a test case containing regex metacharacters. \$\endgroup\$
    – Joey
    Commented Apr 28, 2017 at 7:22

20 Answers 20


Brachylog, 8 bytes


Try it online!

This is really slow. Took about 37 seconds for the "Hello, world!" test case on my PC, and timed-out on TIO.

This takes the string through the Input variable and the list through the Output variable


             String = ?, List = .

             It is possible to find…
~c           …a deconcatenation of ?…
  ¬{   }     …such that it is impossible…
    ∋¬∈      …that an element of that deconcatenation is not an element of .
  • \$\begingroup\$ "la lal al" more than 60 seconds... \$\endgroup\$
    – user58988
    Commented Apr 28, 2017 at 10:25
  • 1
    \$\begingroup\$ @RosLuP With this input and ["la", " l", "al "] as list, it terminated on my computer and correctly answered false. after 6800 seconds, and "only" 113 billion inferences. \$\endgroup\$
    – Fatalize
    Commented Apr 28, 2017 at 13:02
  • \$\begingroup\$ I feel like writing anything in this language would result in a program not runnable on TIO haha. \$\endgroup\$ Commented Apr 28, 2017 at 19:39
  • \$\begingroup\$ @carusocomputing The language is not that slow for most programs, it's just that in some cases due to the declarativeness of the program, it results in very very slow execution times (which could be improved drastically at the cost of code length) \$\endgroup\$
    – Fatalize
    Commented Apr 28, 2017 at 19:41
  • \$\begingroup\$ @Fatalize errr... I meant to say golfing not writing, seems like the fewer instructions, the broader the "question" becomes and the more calculation you need. Seems like an awesome langauge for theoretical math problems. \$\endgroup\$ Commented Apr 28, 2017 at 19:50

Mathematica, 29 bytes



             #,               (* The first argument *)
StringMatchQ[                 (* matches the string pattern *)
               ""|##&         (*   Alternatives *)
                     @@       (*     applied to *)
                       #2     (*     the second argument *)
                         ..   (*   repeated *)

Borderline cheating solution, 21 bytes


Since Mathematica is a symbolic programming language, there is no* difference between the expressions List[a,b,...] and Alternatives[a,b,...] other than how they interact with other symbols and how they are displayed ({a,b,...} and a|b|..., respectively). When used in the second argument of StringMatchQ, an Alternatives expression is treated as a string pattern, and thus we can save 8 bytes over my above solution by taking the second argument as an Alternatives expression.

* Technically List is also Locked, which prevents users from Unprotecting it and changing its behavior.

  • 1
    \$\begingroup\$ {x,y,z} is treated the same as x|y|z for string pattern matching. I think you can replace ""|##&@@#2.. with just #2... \$\endgroup\$
    – Not a tree
    Commented Apr 28, 2017 at 0:24

Pyth, 23 bytes


Takes input like [['string'],['list', 'of', 'parts']]. The output is either an empty list or a list with values inside. In Pyth, a list containing anything, even a null string (['']), evaluates to true.

Try it online!


                             | Implicit: Q = eval(input())
AQ                           | Assign the first value of Q to G and the second to H
  W&GhG                      | While G is not empty and G doesn't contain an empty string:
       J.(G0                 |  Pop the first value of G and store into J
            Vf!xJTH          |  For N in elements in H that match the beginning of J:
                             |   Additional space for suppressing printing 
                    aG>JlN   |   Append to G the elements of J from the length of N to the end
                          ;  | End all loops
                           G | Print G

This solution continuously tries to remove every possible part from the beginning of the string, and keeps track of what values it still needs to look through.

If we look at the value of G in the test case [['ababab'],['a','ba','ab']] after each iteration of the while loop, this is what we get:

['babab', 'abab']
['abab', 'bab']
['bab', 'bab', 'ab']
['bab', 'ab', 'b']
['ab', 'b', 'b']
['b', 'b', '']
['b', '']
['']   <---Remember, this evaluates to True

And, in the test case [['aaaaa'],['aa']], this is what we get:

[]   <---And this evaluates to False

I created another test case, [['aaaaaa'],['a','aa','aaa']] and the output was this:

['', 'aaa', 'aa', 'a', 'aa', 'a', '', 'a', '', 'aa', 'a', '', 'a', '', '', 'a', '', '']

The output list contains a bunch of garbage inside of it, but it's still a truthy value.


Perl 5, 39 bytes

38 bytes of code + -p flag.


Try it online!

For the input "Hello, world!", ["l", "He", "o, wor", "d!"] (separated by newlines actually), it construct the pattern l|He|o, wor|d!| (with the metacharacters escaped, thanks to \Q..\E), and then looks if the first string matches this pattern with /^($v)*$/.

On the TryItOnline, note that there need to be a trailing newline.

  • \$\begingroup\$ "Hello, world! l He o, wor d!" this input with a space after the "l" generate no result \$\endgroup\$
    – user58988
    Commented Apr 28, 2017 at 10:35
  • \$\begingroup\$ @RosLuP Can you give me a TryItOnline link please? (I don't understand what you mean exactly. Note that "false" actually prints nothing as this is Perl) \$\endgroup\$
    – Dada
    Commented Apr 28, 2017 at 11:12
  • \$\begingroup\$ So for false print nothing? In this case excuse me, but this no output value not seems to me too much useful... \$\endgroup\$
    – user58988
    Commented Apr 28, 2017 at 11:19
  • \$\begingroup\$ @RosLuP That's right. In Perl, undef is the falsy value returned by most builtin. And when printing it, it actually prints nothing. And that's exactly what I'm doing. Printing "1/0" is natural for C-like languages, but for Perl, "1/undef" is the natural way. \$\endgroup\$
    – Dada
    Commented Apr 28, 2017 at 11:23
  • \$\begingroup\$ No output has one ambiguity "it is running or already the program end false?" \$\endgroup\$
    – user58988
    Commented Apr 28, 2017 at 12:20

PHP, 69 Bytes



  • \$\begingroup\$ Very clever, took me a minute to understand what you're doing. +1 for thinking outside the box \$\endgroup\$
    – Martijn
    Commented Apr 28, 2017 at 10:39
  • \$\begingroup\$ False negative for that pesky edge case ["", ["The string can be constructed with nothing!"]] \$\endgroup\$ Commented Apr 29, 2017 at 20:40
  • \$\begingroup\$ @JonathanAllan done is an empty string a string? \$\endgroup\$ Commented Apr 29, 2017 at 20:56
  • \$\begingroup\$ Yeah, the problem of empty partitioning is an issue in many solutions. \$\endgroup\$ Commented Apr 29, 2017 at 20:59

Python 2, 141 bytes

lambda s,l:s in[''.join(i)for r in range(len(s)+1)for j in combinations_with_replacement(l,r)for i in permutations(j)]
from itertools import*

Try it Online!

Extremely inefficient. The first test case times out on TIO.


JavaScript (ES6), 59 bytes

Takes the array of substrings a and the string s in currying syntax (a)(s). Returns false / true.



a =>                          // main function that takes 'a' as input
  g = s =>                    // g = recursive function that takes 's' as input
    !s ||                     // if 's' is empty, return true (success!)
    a.some(e =>               // else, for each element 'e' in 'a':
      s.split(e)[0] ?         //   if 's' doesn't begin with 'e':
        0                     //     do nothing
      :                       //   else:
        g(s.slice(e.length))  //     remove 'e' at the beginning of 's' and
    )                         //     do a recursive call on the remaining part

Test cases

let f =


console.log(f(["l", "He", "o, wor", "d!"])("Hello, world!"))        // true
console.log(f(["la", " l", "al "])("la lal al "))                   // true
console.log(f(["this should return falsy"])("this is a string"))    // false
console.log(f(["this", "i i", " a", " string"])("thi is a string")) // false
console.log(f(["aa"])("aaaaa"))                                     // false
console.log(f(["foo", "bar", " ", "spam"])("foo bar foobar"))       // true
console.log(f(["a","ba","ab"])("ababab"))                           // true


Haskell, 35 bytes

# takes a String and a list of Strings, and returns a Bool.

s#l=elem s$concat<$>mapM("":)(l<$s)

Try it online!

Just don't mind the test case I left out because it thrashed my meager laptop, even with -O2. I suspect GHC doesn't fuse away that intermediate 30517578125 element list, it has too much sharing to get swiftly garbage collected, and because the test case is false the program has to generate all of it... feel free to try if you can handle that.

mapM("":)(l<$s) is a list of all ways of making a length s list of elements that are either empty strings or strings from l.


Pyth, 17 15 11 14 bytes


The requirement for the empty string changed, adding 3 bytes.


AQ                     Save the input into G, H.
           ./G         Get all partitions of G.
       m-dH            Check if the parts are in H.
     }Y                The empty list should be present if and only
                           if the string can be made...
  |!G                  ... or the string might be empty.

Old versions


Shorter and runs in the lifespan of the universe!


AQ                  Save the input into G, H.
        ./G         Get all partitions of G.
    m-dH            Check if the parts are in H.
  }Y                The empty list should be present if and only
                        if the string can be made.


This is horrifyingly slow, but it works for my (trivially small) test cases.


AQ                  Save the input into G, H.
             *HlG   Repeat the list of substrings for each character of G.
            y       Take the power set.
         .pM        Take every permutation of each set of substrings.
      sMs           Get a list of all the joined strings.
    }G              Check if G is one of them.
  &G                Make sure G is not empty.

Jelly, 14 12 8 bytes


Try it online!

How it works

;FŒṖḟ€Ạ¬   - main function, left argument s, right argument l
;F         - concatenate to the string the list, flattened to deal with "" as string
  ŒṖ       - Get all partitions of s, that is, all ways to make s from substrings
     €     - For each partition...
    ḟ      -   Filter out (exclude) those elements which are not in... 
           -   (implicit right arg) the list l. This leaves the empty set (falsy) if the partition can be made of elements from the list
      Ạ    - If any element is falsy (thus constructable from l), return 0; else return 1
       ¬   - Apply logical not to this, to yield the proper 1 = constructable from list, 0 otherwise.

bugfix on case "", ["The string can be constructed with nothing"] thanks to @JonathanAllan

  • \$\begingroup\$ False negative for "", ["The string can be constructed with nothing!"] \$\endgroup\$ Commented Apr 29, 2017 at 19:54
  • \$\begingroup\$ It'll be much slower but ;FŒṖḟ⁹$€Ạ¬ would fix it. \$\endgroup\$ Commented Apr 29, 2017 at 20:05
  • \$\begingroup\$ ...and you can use an implicit right argument for , so you dont need the $ or the : ;FŒṖḟ€Ạ¬. \$\endgroup\$ Commented Apr 29, 2017 at 20:08
  • \$\begingroup\$ Grr, that's what I get for not testing every single testcase. I might be able to maintain 8 bytes by replacing ¬ with an operation which always returns true with right argument "". \$\endgroup\$ Commented Apr 29, 2017 at 20:08
  • \$\begingroup\$ ^ well I got it back to 8 :) \$\endgroup\$ Commented Apr 29, 2017 at 20:09

R, 49 bytes


Try it online!

  • 2
    \$\begingroup\$ Should fail for ('x', '.'), but doesn't. \$\endgroup\$
    – Joey
    Commented Apr 28, 2017 at 7:32

Pyth, 10 8 bytes


Test suite

This takes the list on the first line of STDIN, and the string (without quotes) on the second.

To start, the list is stored in Q, and the string is stored in z. Next, we form all possible partitions of z. Each partition will be filtered (f) to check if it uses only pieces in Q. To do this, we remove all elements of Q from T, the partition we're partitioning, and logically negate the result with !, so that only partitions where every element was in Q are kept.

To fix the problem that '' has no partitions, we add the first word of the dictionary to z, so that it won't be an empty string.

  • \$\begingroup\$ The test suite misses the bottom line (an empty string) - Does it need quoting? With an empty line or "" it seems to fail that case. \$\endgroup\$ Commented Apr 29, 2017 at 20:34
  • \$\begingroup\$ An empty string has no partitions, so it actually just gives the wrong answer here. Darn, I'll try to fix it. \$\endgroup\$
    – isaacg
    Commented Apr 29, 2017 at 21:32
  • \$\begingroup\$ The fix I suggested for Jelly was to concatenate the input string with the input array flattened, maybe you can do the same? \$\endgroup\$ Commented Apr 29, 2017 at 22:03
  • \$\begingroup\$ @JonathanAllan I did something similar, thanks. \$\endgroup\$
    – isaacg
    Commented Apr 29, 2017 at 22:45
  • \$\begingroup\$ The cases of "", [""] and "", [] have not been covered - lets not go there :) \$\endgroup\$ Commented Apr 29, 2017 at 22:54

PowerShell, 61 58 57 bytes

{$s,$l=$_;$l|sort -d length|%{$s=$s.replace($_,'')};+!$s}

Try it online!

Old solutions:

{$s,$l=$_;$l|sort -d length|%{$s=$s.replace($_,'')};[int]!$s}
{$s,$l=$_;$l|sort -d length|%{$s=$s.replace($_,'')};0+!$s}  
  • \$\begingroup\$ This one is almost unreadable, so I'd reccommend changing it a bit. I'm fairly certain most other people would agree. \$\endgroup\$
    – Riker
    Commented Apr 30, 2017 at 21:55
  • \$\begingroup\$ Thank you for the explanation of the reason of your correction of my solution. \$\endgroup\$ Commented May 1, 2017 at 4:13

Python 2, 64 bytes

lambda s,l:len(re.findall("^("+"|".join(l)+")*$",s))>0
import re

Try this online!

  • \$\begingroup\$ I think this doesn't totally work, try ("aaaaaaa",["aa","aaa"]). \$\endgroup\$
    – xnor
    Commented Apr 28, 2017 at 1:44
  • \$\begingroup\$ @xnor I updated it. Come to find out, regex is perfect for this. \$\endgroup\$
    – Neil
    Commented Apr 28, 2017 at 3:55
  • 4
    \$\begingroup\$ Should fail for ('x', '.'), I guess, but doesn't. \$\endgroup\$
    – Joey
    Commented Apr 28, 2017 at 7:31
  • 1
    \$\begingroup\$ @nfnneil Did you? Your last edit was 10 hours ago. \$\endgroup\$
    – Dennis
    Commented Apr 28, 2017 at 14:25
  • 1
    \$\begingroup\$ ...or "Hello", ["\w"] etc. \$\endgroup\$ Commented Apr 29, 2017 at 20:30

PowerShell, 78

$s,$l=$args;!($s-creplace(($l|sort -d length|%{[regex]::escape($_)})-join'|'))

Pretty straightforward regex-based approach.


CJam (16 bytes)


This is an anonymous block (function) taking the string and the array of strings on the stack. Online demo.

It uses the obvious algorithm:

{        e# Declare a block. Call the args str and arr
  Ma+    e#   Add the empty string to the array
  1$,m*  e#   Take the Cartesian product of len(str) copies of (arr + [""])
  :e_    e#   Flatten each element of the Cartesian product into a single string
  \a&    e#   Intersect with an array containing only str

The return value is an empty array/string (falsy) if str can't be made, or an array containing str (truthy, even if str is itself the empty string) if it can be made.

  • \$\begingroup\$ @RosLuP, I'm not sure what you mean. That particular test case executes so fast that I can't actually time it. Other test cases do take a long time to execute, but the spec doesn't include any time constraints. \$\endgroup\$ Commented Apr 28, 2017 at 10:47
  • \$\begingroup\$ @RosLuP, online demo. But I don't understand what your complaint is. \$\endgroup\$ Commented Apr 28, 2017 at 11:54

C++(Bcc), 287 bytes

f(a,b)char*a,**b;{int i,j,k,v,p[256];if(!a||!b||!*b)return-1;for(v=0;v<256&&b[v];++v)p[v]=v;if(v>=256)return-1;la:for(i=0,j=0;j<v&&a[i];){for(k=0;b[p[j]][k]==a[i]&&a[i];++i,++k);j=b[p[j]][k]?(i-=k),j+1:0;}if(a[i]&&next_permutation(p,p+v)) goto la;return i&&!a[i];}

because i do not wrote or used too much the next_permutation() i don't know if is all ok. I don't know 100% if it is a solution too possibly this is out of quality... One list of string is here one array of pointers to char; NULL terminated The algo is easy, there is one algo that linearity try if all string in the list fit with argument "a" string there is one other algo that permute the index of the list of string so it try all possible combination.

ungolf it, test code and results here

{int i,j,k,v,p[256];
 if(!a||!b||!*b) return -1;
 for(v=0;v<256&&b[v];++v) p[v]=v;
 if(v>=256)      return -1; // one array of len >256 is too much
 if(a[i]&&next_permutation(p,p+v)) goto la;
 return i&&!a[i];  

#define F for
#define P printf

test(char* a, char** b)
{int i;
       P("\"%s\"%s", b[i], b[i+1]?", ":"");
 P("])=%d\n", f(a,b));

{char *a1="Hello, world!",    *b1[]={"l","He", "o, worl", "d!",      0};//1
 char *a2="la lal al ",       *b2[]={"la", " l", "al ",              0};//1
 char *a3="this is a string", *b3[]={"this should return falsy",     0};//0
 char *a4="thi is a string",  *b4[]={"this", "i i", " a", " string", 0};//0
 char *a5="aaaaa",            *b5[]={"aa",                           0};//0
 char *a6="foo bar foobar",   *b6[]={"foo","bar"," ","spam",         0};//1
 char *a7="ababab",           *b7[]={"a","ba","ab",                  0};//1
 char *a8="",                 *b8[]={"This return 0 even if has to return 1", 0};//0
 char *a9="ababc",            *b9[]={"a","abc", "b", 0};//1


f("Hello, world!",["l", "He", "o, worl", "d!"])=1
f("la lal al ",["la", " l", "al "])=1
f("this is a string",["this should return falsy"])=0
f("thi is a string",["this", "i i", " a", " string"])=0
f("foo bar foobar",["foo", "bar", " ", "spam"])=1
f("ababab",["a", "ba", "ab"])=1
f("",["This return 0 even if has to return 1"])=0
f("ababc",["a", "abc", "b"])=1

this would compile in gcc C++ compiler


int f(char*a,char**b){int i,j,k,v,p[256];if(!a||!b||!*b)return -1;for(v=0;v<256&&b[v];++v)p[v]=v;if(v>=256)return -1;la:;for(i=0,j=0;j<v&&a[i];){for(k=0;b[p[j]][k]==a[i]&&a[i];++i,++k);j=b[p[j]][k]?(i-=k),j+1:0;}if(a[i]&&std::next_permutation(p,p+v))goto la;return i&&!a[i];}
  • \$\begingroup\$ Gotta love C++! :) \$\endgroup\$
    – MEMark
    Commented Apr 29, 2017 at 6:50

Python, 66 bytes

lambda s,l:s==''or any(x==s[:len(x)]and f(s[len(x):],l)for x in l)


def f(s,l):
    if s=='': 
        return 1
    for x in l:
        if s.startswith(x) and f(s[len(x):],l):
            return 1
    return 0

Microsoft Sql Server, 353 bytes

u as(select s.n,s collate Latin1_General_BIN s,l collate Latin1_General_BIN l,
row_number()over(partition by l.n order by len(l)desc)r from s,l where s.n=l.n),
v as(select n,s,l,replace(s,l,'')c,r from u where r=1 union all
select u.n,u.s,u.l,replace(v.c,u.l,''),u.r from v,u where v.n=u.n and v.r+1=u.r)
select s,iif(min(c)='',1,0)u from v group by n,s

Test it online.

Readable version:

with s as(
  select n,s
  from(values(1,'Hello, world!'),
             (2,'la lal al '),
             (3,'this is a string'),
             (4,'thi is a string'),
             (6,'foo bar foobar'),
l as(
  select n,l
  from(values(1,'l'),(1,'He'),(1,'o, wor'),(1,'d!'),
             (2,'la'),(2,' l'),(2,'al '),
             (3,'this should return falsy'),
             (4,'this'),(4,'i i'),(4,' a'),(4,' string'),
             (6,'foo'),(6,'bar'),(6,' '),(6,'spam'),
             (8,'The string can be constructed with nothing!'))l(n,l)),
--The solution starts from the next line.
u as(
  select s.n,
    s collate Latin1_General_BIN s,
    l collate Latin1_General_BIN l,
    row_number()over(partition by l.n order by len(l)desc)r
  from s,l
  where s.n=l.n),
v as(
  select n,s,l,replace(s,l,'')c,r from u where r=1
    union all
  select u.n,u.s,u.l,replace(v.c,u.l,''),u.r
  from v,u
  where v.n=u.n and v.r+1=u.r
select s,iif(min(c)='',1,0)u from v group by n,s

C, 140 bytes

I'm sure there is a shorter way to do this in C but I wanted to create a solution that tests all the possible combinations of substrings instead of the usual find/replace method.

char p[999];c,o;d(e,g,l,f)int*e,**g,**l;{c=f&&c;for(l=g;*l;)strcpy(p+f,*l++),(o=strlen(p))<strlen(e)?d(e,g,0,o):(c|=!strcmp(e,p));return c;}

Try it online


#include <string.h>
#include <stdio.h>

char buf[999];
int result;
int temp;

int test(char *text, char **ss, char **ptr, int length) 
    if (length == 0)
        result = 0;

    for(ptr = ss; *ptr; ptr++)
        strcpy(buf + length, *ptr);
        temp = strlen(buf);
        if (temp < strlen(text))
            // test recursivly
            test(text, ss, 0, temp);
            if (strcmp(buf, text) == 0)
                result = 1;
    return result;

int main()
    char *text = "Hello,World";
    char *keywords[] = { "World", "Hello", ",", 0 };
    printf("%d", test(text, keywords, 0, 0));

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.