Bestimmen Sie anhand einer Zeichenfolge sund eines Arrays / einer Liste l, ob sTeile aus erstellt werden können oder nicht l.

Wenn die Zeichenfolge beispielsweise "Hello, world!"und die Liste die Zeichenfolge ist [' world!', 'Hello,'], sollte das Programm / die Funktion einen Wahrheitswert zurückgeben, da Sie die Liste so anordnen können, dass sie die Zeichenfolge bildet. Die folgende Liste würde auch einen truthy Wert zurück: ['l', 'He', 'o, wor', 'd!']. Stellen Sie sich die 'l'Füllung dort vor, wo sie in der Saite benötigt wird. Also ja, Sie können Elemente der Liste wiederholen, um die Zeichenfolge zu bilden. Wenn die Zeichenfolge nicht gebildet werden kann, sollte ein falscher Wert zurückgegeben werden. Standardmethoden der E / A, Standardlücken gelten.

Testfälle:

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

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

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

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

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

"aaaaa", ["aa"]
0

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

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

"", ["The string can be constructed with nothing!"]
1

Brachylog , 8 Bytes

~c¬{∋¬∈}

Probieren Sie es online!

Das ist wirklich langsam. Dauerte etwa 37 Sekunden für die "Hallo, Welt!" Testfall auf meinem PC und Timeout auf TIO.

Dies führt die Zeichenfolge durch die Eingabevariable und die Liste durch die Ausgabevariable

Erläuterung

             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 .

Mathematica, 29 Bytes

StringMatchQ[#,""|##&@@#2..]&

Erläuterung:

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

Borderline-Cheat-Lösung, 21 Bytes

StringMatchQ[#,#2..]&

Da Mathematica eine symbolische Programmiersprache ist, gibt es keine * Unterschied zwischen den Ausdrücken List[a,b,...]und Alternatives[a,b,...]anders als wie sie interagieren mit anderen Symbolen und wie sie angezeigt werden ( {a,b,...}und a|b|...sind). Wenn StringMatchQein AlternativesAusdruck im zweiten Argument von verwendet wird , wird er als Zeichenfolgenmuster behandelt, und daher können wir 8Bytes gegenüber der obigen Lösung sparen, indem wir das zweite Argument als AlternativesAusdruck verwenden.

* Technisch Listist es auch so Locked, dass Benutzer daran Unprotectgehindert werden, es zu bearbeiten und sein Verhalten zu ändern.

Pyth, 23 Bytes

AQW&GhGJ.(G0Vf!xJTH aG>JlN;G

Nimmt Eingaben wie [['string'],['list', 'of', 'parts']]. Die Ausgabe ist entweder eine leere Liste oder eine Liste mit Werten darin. In Pyth wird eine Liste, die alles enthält, sogar eine Nullzeichenfolge ( ['']), als wahr ausgewertet.

Probieren Sie es online!

Erläuterung:

                             | 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

Diese Lösung versucht kontinuierlich, jeden möglichen Teil vom Anfang der Zeichenfolge zu entfernen, und verfolgt, welche Werte noch durchgesehen werden müssen.

Wenn wir uns nach jeder Iteration der while-Schleife den Wert von Gim Testfall ansehen [['ababab'],['a','ba','ab']], erhalten wir Folgendes:

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

Und im Testfall erhalten [['aaaaa'],['aa']]wir Folgendes:

['aaaaa']
['aaa']
['a']
[]   <---And this evaluates to False

Ich habe einen weiteren Testfall erstellt [['aaaaaa'],['a','aa','aaa']]und folgende Ausgabe erhalten:

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

Die Ausgabeliste enthält eine Menge Müll, aber es ist immer noch ein wahrer Wert.

Perl 5 , 39 Bytes

38 Byte Code + -pFlag.

map{chop;$v.="\Q$_\E|"}<>;$_=/^($v)*$/

Probieren Sie es online!

Für die Eingabe "Hello, world!", ["l", "He", "o, wor", "d!"](tatsächlich durch Zeilenumbrüche getrennt) wird das Muster erstellt l|He|o, wor|d!|(wobei die Metazeichen dank von maskiert werden) \Q..\Eund dann geprüft, ob die erste Zeichenfolge mit diesem Muster übereinstimmt /^($v)*$/.

Beachten Sie bei TryItOnline, dass eine nachgestellte Zeile vorhanden sein muss.

PHP, 69 Bytes

<?=($s=$_GET[0])>""?ctype_digit(strtr($s,array_flip($_GET[1])))?:0:1;

Testfälle

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*

Probieren Sie es online!

Extrem ineffizient. Der erste Testfall läuft bei TIO ab.

JavaScript (ES6), 59 Byte

Übernimmt das Array von Teilzeichenfolgen aund die Zeichenfolge sin der aktuellen Syntax (a)(s). Rückgabe false/ true.

a=>g=s=>!s||a.some(e=>s.split(e)[0]?0:g(s.slice(e.length)))

Kommentiert

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

Testfälle

let f =

a=>g=s=>!s||a.some(e=>s.split(e)[0]?0:g(s.slice(e.length)))

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

#Nimmt a Stringund eine Liste von Strings und gibt a zurück Bool.

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

Probieren Sie es online!

Aber stört euch nicht an dem Testfall, den ich ausgelassen habe, weil er meinen dürftigen Laptop selbst mit -O2 kaputt gemacht hat. Ich vermute, dass GHC diese Liste der Zwischenelemente nicht verwirbelt, es hat zu viel Sharing, um schnell Müll zu sammeln, und weil der Testfall falsch ist, muss das Programm alles generieren ... Sie können es gerne versuchen, wenn Sie können Regle dies.

mapM("":)(l<$s)ist eine Liste aller Möglichkeiten, eine length sListe von Elementen zu erstellen, aus denen entweder leere Zeichenfolgen oder Zeichenfolgen bestehen l.

Pyth, 17 15 11 14 Bytes

AQ|!G}Ym-dH./G

Die Anforderung für die leere Zeichenfolge wurde geändert und 3 Byte hinzugefügt.

Erläuterung

AQ|!G}Ym-dH./G
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.

alte Versionen

AQ}Ym-dH./G

Kürzer und läuft in der Lebensdauer des Universums!

Erläuterung

AQ}Ym-dH./G
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.

AQ&G}GsMs.pMy*HlG

Das ist schrecklich langsam, aber es funktioniert für meine (trivial kleinen) Testfälle.

Erläuterung

AQ&G}GsMs.pMy*HlG
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

;FŒṖḟ€Ạ¬

Probieren Sie es online!

Wie es funktioniert

;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 für den Fall "", ["The string can be constructed with nothing"]dank @JonathanAllan

R, 49 Bytes

function(s,l)gsub(paste(l,collapse='|'),"",s)==""

Probieren Sie es online!

Pyth, 10 8 Bytes

f!-TQ./+zh

Testsuite

Dies nimmt die Liste in der ersten Zeile von STDIN und die Zeichenfolge (ohne Anführungszeichen) in der zweiten.

Zu Beginn wird die Liste in gespeichert Q, und die Zeichenfolge wird in gespeichert z. Als nächstes bilden wir alle möglichen Partitionen von z. Jede Partition wird gefiltert ( f), um zu überprüfen, ob sie nur Teile enthält Q. Dazu entfernen wir alle Elemente Qaus T, die Partition wir sind Partitionierung und negieren logisch das Ergebnis mit !, so dass nur Partitionen , wobei jedes Element war inQ gehalten werden.

Um das Problem zu beheben, ''das keine Partitionen enthält, fügen wir das erste Wort des Wörterbuchs zu z hinzu, damit es keine leere Zeichenfolge ist.

PowerShell, 61 58 57 Byte

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

Probieren Sie es online!

Alte Lösungen:

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

Python 2, 64 Bytes

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

Versuchen Sie dies online!

PowerShell, 78

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

Ziemlich unkomplizierter, auf Regex basierender Ansatz.

CJam (16 Bytes)

{Ma+1$,m*:e_\a&}

Dies ist ein anonymer Block (eine Funktion), der die Zeichenfolge und das Array von Zeichenfolgen auf dem Stapel aufnimmt. Online-Demo .

Es verwendet den offensichtlichen Algorithmus:

{        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
}

Der Rückgabewert ist ein leeres Array / eine leere Zeichenfolge (falsch), falls strdies nicht möglich ist, oder ein Array mit str(wahrheitsgemäß, auch wenn stres sich um eine leere Zeichenfolge handelt), falls dies möglich ist.

C ++ (Bcc), 287 Bytes

#include<algorithm.h>
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];}

weil ich die next_permutation () nicht zu oft geschrieben oder benutzt habe, weiß ich nicht, ob alles in Ordnung ist. Ich weiß nicht zu 100%, ob es sich möglicherweise um eine zu schlechte Lösung handelt. Eine Liste mit Zeichenfolgen enthält eine Reihe von Zeigern auf Zeichen. NULL terminiert Das Algo ist einfach, es gibt ein Algo, dessen Linearität versucht wird, wenn alle Zeichenfolgen in der Liste mit dem Argument "a" übereinstimmen. Es gibt ein anderes Algo, das den Index der Liste der Zeichenfolgen durchläuft, sodass alle möglichen Kombinationen versucht werden.

ungolf it, test code und ergebnisse hier

#include<stdio.h>
g(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; // one array of len >256 is too much
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];  
}

#define F for
#define P printf

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

main()
{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

  test(a1,b1);test(a2,b2);test(a3,b3);test(a4,b4);test(a5,b5);test(a6,b6);
  test(a7,b7);test(a8,b8);test(a9,b9);
}

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("aaaaa",["aa"])=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

Dies würde im GCC C ++ - Compiler kompiliert

#include<algorithm>

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];}

Python, 66 Bytes

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

Ungolfed:

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

Testen Sie es online.

Lesbare 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'),
             (5,'aaaaa'),
             (6,'foo bar foobar'),
             (7,'ababab'),
             (8,''))s(n,s)),
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'),
             (5,'aa'),
             (6,'foo'),(6,'bar'),(6,' '),(6,'spam'),
             (7,'a'),(7,'ba'),(7,'ab'),
             (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

Ich bin sicher, dass es einen kürzeren Weg gibt, dies in C zu tun, aber ich wollte eine Lösung erstellen, die alle möglichen Kombinationen von Teilzeichenfolgen anstelle der üblichen Find / Replace-Methode testet.

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;}

Probieren Sie es online aus

Ungolfed:

#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);
        }
        else
        {
            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));
}