W teorii informacji „kod prefiksu” to słownik, w którym żaden z kluczy nie jest prefiksem innego. Innymi słowy, oznacza to, że żaden ciąg nie zaczyna się od żadnego z pozostałych.

Na przykład {"9", "55"}jest kodem prefiksu, ale {"5", "9", "55"}nie jest.

Największą zaletą tego jest to, że zakodowany tekst można zapisać bez separatora między nimi i nadal będzie on wyjątkowo czytelny. Widać to w algorytmach kompresji, takich jak kodowanie Huffmana , które zawsze generuje optymalny kod prefiksu.

Twoje zadanie jest proste: na podstawie listy ciągów określ, czy jest to prawidłowy kod prefiksu.

Twój wkład:

• Będzie listą ciągów znaków w dowolnym rozsądnym formacie .

• Będzie zawierać tylko drukowalne ciągi ASCII.

• Nie będzie zawierać żadnych pustych ciągów.

Twój wynik będzie miał wartość true / falsey : Prawda, jeśli jest to poprawny kod prefiksu, i falsey, jeśli nie jest.

Oto kilka prawdziwych przypadków testowych:

["Hello", "World"]                      
["Code", "Golf", "Is", "Cool"]
["1", "2", "3", "4", "5"]
["This", "test", "case", "is", "true"]          

["111", "010", "000", "1101", "1010", "1000", "0111", "0010", "1011", 
 "0110", "11001", "00110", "10011", "11000", "00111", "10010"]

Oto kilka fałszywych przypadków testowych:

["4", "42"]                             
["1", "2", "3", "34"]                   
["This", "test", "case", "is", "false", "t"]
["He", "said", "Hello"]
["0", "00", "00001"]
["Duplicate", "Duplicate", "Keys", "Keys"]

Jest to kod-golf, więc obowiązują standardowe luki i wygrywa najkrótsza odpowiedź w bajtach.

Pyth, 8 bajtów

.AxM.PQ2

Zestaw testowy

Weź wszystkie 2 elementy permutacji danych wejściowych, zamapuj każdy na indeks jednego ciągu w drugim (0 dla prefiksu) i zwróć, czy wszystkie wyniki są prawdziwe (niezerowe).

Haskell, 37 bajtów

f l=[x|x<-l,y<-l,zip x x==zip x y]==l

Każdy element xz ljest powtarzany raz dla każdego elementu, który jest to prefiks, który jest dokładnie jeden raz na liście prefix-wolny, dając oryginalną listę. Właściwość prefiksu jest sprawdzana przez skompresowanie obu list za pomocą x, co odcina elementy o długości przekraczającej x.

Java, 128 127 126 125 124 121 bajtów

(Dzięki @Kenny Lau, @Maltysen, @Patrick Roberts, @Joba)

Object a(String[]a){for(int i=0,j,l=a.length;i<l;i++)for(j=0;j<l;)if(i!=j&a[j++].startsWith(a[i]))return 1<0;return 1>0;}

Bez golfa

Object a(String[] a) {
    for (int i = 0, j, l = a.length; i < l; i++) 
        for (j = 0; j < l;) 
            if (i != j & a[j++].startsWith(a[i])) return 1<0;
    return 1>0;
}

Wydajność

[Hello, World]
true

[Code, Golf, Is, Cool]
true

[1, 2, 3, 4, 5]
true

[This, test, case, is, true]
true

[111, 010, 000, 1101, 1010, 1000, 0111, 0010, 1011, 0110, 11001, 00110, 10011, 11000, 00111, 10010]
true

[4, 42]
false

[1, 2, 3, 34]
false

[This, test, case, is, false, t]
false

[He, said, Hello]
false

[0, 00, 00001]
false

[Duplicate, Duplicate, Keys, Keys]
false

Python 2, 48 51 bajtów

lambda l:all(1/map(a.find,l).count(0)for a in l)

Dla każdego elementu az lfunkcja a.findznajduje indeks pierwszego wystąpienia aw ciągu wejściowego, dzięki czemu -1w nieobecności. Tak, 0oznacza prefiks. Na liście wolnej od prefiksów mapowanie tej funkcji zwraca tylko jeden 0dla asiebie. Funkcja sprawdza, czy tak jest w każdym przypadku a.

51 bajtów:

lambda l:[a for a in l for b in l if b<=a<b+'~']==l

Zamień ~na znak o kodzie ASCII 128 lub wyższym.

Dla każdego elementu aw lkopia jest włączone dla każdego elementu, który jest prefiksem niego. W przypadku listy bez prefiksów jedynym takim elementem jest asam, więc daje to oryginalną listę.

CJam, 14 bajtów

q~$W%2ew::#0&!

Zestaw testowy.

Wyjaśnienie

q~   e# Read and evaluate input.
$    e# Sort strings. If a prefix exists it will end up directly in front 
     e# of a string which contains it.
W%   e# Reverse list.
2ew  e# Get all consecutive pairs of strings.
::#  e# For each pair, find the first occurrence of the second string in the first.
     e# If a prefix exists that will result in a 0, otherwise in something non-zero.
0&   e# Set intersection with 0, yielding [0] for falsy cases and [] for truthy ones.
!    e# Logical NOT.

JavaScript ES6, 65 43 40 bajtów

a=>!/(.*)\1/.test(''+a.sort().join``)
      ^            ^               ^ embedded NUL characters

Moje poprzednie rozwiązanie, które obsługiwało tablice ciągów wszystkich znaków UTF-8:

a=>!/[^\\]("([^"]*\\")*[^\\])",\1/.test(JSON.stringify(a.sort()))

Byłem w stanie uniknąć JSON.stringify ponieważ wyzwanie określa tylko drukowalne znaki ASCII.

Test

f=a=>!/(\0.*)\1/.test('\0'+a.sort().join`\0`) // since stackexchange removes embedded NUL characters

O.textContent += 'OK: '+
[["Hello", "World"]                      
,["Code", "Golf", "Is", "Cool"]
,["1", "2", "3", "4", "5"]
,["This", "test", "case", "is", "true"]          
,["111", "010", "000", "1101", "1010", "1000", "0111", "0010", "1011", 
 "0110", "11001", "00110", "10011", "11000", "00111", "10010"]
].map(a=>f(a)) 

O.textContent += '\nKO: '+
[["4", "42"]                             
,["1", "2", "3", "34"]                   
,["This", "test", "case", "is", "false", "t"]
,["He", "said", "Hello"]
,["0", "00", "00001"]
,["Duplicate", "Duplicate", "Keys", "Keys"]
].map(a=>f(a))

<pre id=O></pre>

Haskell, 49 bajtów

g x=[1|z<-map((and.).zipWith(==))x<*>x,z]==(1<$x)

To składa się z kilku części:

-- Are two lists (or strings) equal for their first min(length_of_1,length_of_2) elements, i.e. is one the prefix of the other?
(and.).zipWith(==)

-- Check whether one element is the prefix of the other, for all pairs of elements (including equal pairs)
map((and.).zipWith(==))x<*>x

-- This is a list of 1's of length (number of elements that are the prefix of the other)
[1|z<-map((and.).zipWith(==))x<*>x,z]

-- This is the input list, with all the elements replaced with 1's
(1<$x)

Jeśli dwie listy są równe, element jest tylko przedrostkiem samego siebie i jest prawidłowy.

Retina , 19 bajtów

Liczba bajtów zakłada kodowanie ISO 8859-1.

O`.+
Mm1`^(.+)¶\1
0

Wejście powinno być oddzielone od linii. Wyjście dotyczy 0fałszu i 1prawdy.

Wypróbuj online! (Nieznacznie zmodyfikowano, aby obsługiwał wiele przypadków testowych oddzielonych spacjami).

Wyjaśnienie

O`.+

Posortuj linie na wejściu. Jeśli prefiks istnieje, kończy się bezpośrednio przed ciągiem, który go zawiera.

Mm1`^(.+)¶\1

Spróbuj dopasować ( M) pełną linię, która znajduje się również na początku następnej linii. mAktywuje tryb multilinii takie, że ^początki linii mecze i 1zapewnia, że tylko my liczyć co najwyżej jeden mecz tak, że wyjście jest 0albo 1.

0

Do zamiany 0i 1w związku z tym liczyć liczbę 0s.

Java, 97 bajtów

Object a(String[]a){for(String t:a)for(String e:a)if(t!=e&t.startsWith(e))return 1<0;return 1>0;}

Wykorzystuje większość sztuczek znalezionych w odpowiedzi @ Marv , ale korzysta również z pętli foreach i równości referencji łańcucha.

Unminified:

Object a(String[]a){
    for (String t : a)
        for (String e : a)
            if (t != e & t.startsWith(e))
                return 1<0;
    return 1>0;
}

Zauważ, że, jak powiedziałem, używa to równości referencji ciągów. Oznacza to, że kod może zachowywać się dziwnie z powodu internowania String . Kod działa, gdy używa się argumentów przekazywanych z wiersza poleceń, a także gdy używa się czegoś odczytanego z wiersza poleceń. Jeśli jednak chcesz na stałe zakodować wartości do przetestowania, musisz ręcznie wywołać konstruktor String, aby wymusić, że internowanie się nie pojawi:

System.out.println(a(new String[] {new String("Hello"), new String("World")}));
System.out.println(a(new String[] {new String("Code"), new String("Golf"), new String("Is"), new String("Cool")}));
System.out.println(a(new String[] {new String("1"), new String("2"), new String("3"), new String("4"), new String("5")}));
System.out.println(a(new String[] {new String("This"), new String("test"), new String("case"), new String("is"), new String("true")}));
System.out.println(a(new String[] {new String("111"), new String("010"), new String("000"), new String("1101"), new String("1010"), new String("1000"), new String("0111"), new String("0010"), new String("1011"), new String("0110"), new String("11001"), new String("00110"), new String("10011"), new String("11000"), new String("00111"), new String("10010")}));
System.out.println(a(new String[] {new String("4"), new String("42")}));
System.out.println(a(new String[] {new String("1"), new String("2"), new String("3"), new String("34")}));
System.out.println(a(new String[] {new String("This"), new String("test"), new String("case"), new String("is"), new String("false"), new String("t")}));
System.out.println(a(new String[] {new String("He"), new String("said"), new String("Hello")}));
System.out.println(a(new String[] {new String("0"), new String("00"), new String("00001")}));
System.out.println(a(new String[] {new String("Duplicate"), new String("Duplicate"), new String("Keys"), new String("Keys")}));

PostgreSQL, 186 , 173 bajtów

WITH y AS(SELECT * FROM t,LATERAL unnest(c)WITH ORDINALITY s(z,r))
SELECT y.c,EVERY(u.z IS NULL)
FROM y LEFT JOIN y u ON y.i=u.i AND y.r<>u.r AND y.z LIKE u.z||'%' GROUP BY y.c

Wydajność:

Tym razem nie ma demo na żywo. http://sqlfiddle.com obsługuje tylko 9.3 i do uruchomienia tej wersji demo 9.4 jest wymagana.

Jak to działa:

1. Podziel tablicę ciągów na numer i nazwij ją y
2. Zdobądź całe y
3. LEFT OUTER JOINdo tej samej tabeli pochodnej opartej na tym samym i(id), ale z różnymi, oridinalktóre zaczynają się od przedrostkay.z LIKE u.z||'%'
4. Wynik grupy na podstawie c(tablica początkowa) i użyj EVERYfunkcji grupowania. Jeśli każdy wiersz z drugiej tabeli IS NULLoznacza, że ​​nie ma przedrostków.

Wprowadź, jeśli ktoś jest zainteresowany:

CREATE TABLE t(i SERIAL,c text[]);

INSERT INTO t(c)
SELECT '{"Hello", "World"}'::text[]
UNION ALL SELECT  '{"Code", "Golf", "Is", "Cool"}'
UNION ALL SELECT  '{"1", "2", "3", "4", "5"}'
UNION ALL SELECT  '{"This", "test", "case", "is", "true"}'         
UNION ALL SELECT  '{"111", "010", "000", "1101", "1010", "1000", "0111", "0010", "1011","0110", "11001", "00110", "10011", "11000", "00111", "10010"}'
UNION ALL SELECT  '{"4", "42"}'
UNION ALL SELECT  '{"1", "2", "3", "34"}'                   
UNION ALL SELECT  '{"This", "test", "case", "is", "false", "t"}'
UNION ALL SELECT  '{"He", "said", "Hello"}'
UNION ALL SELECT  '{"0", "00", "00001"}'
UNION ALL SELECT  '{"Duplicate", "Duplicate", "Keys", "Keys"}';

EDYTOWAĆ:

SQL Server 2016+ realizacja:

WITH y AS (SELECT *,z=value,r=ROW_NUMBER()OVER(ORDER BY 1/0) FROM #t CROSS APPLY STRING_SPLIT(c,','))
SELECT y.c, IIF(COUNT(u.z)>0,'F','T')
FROM y LEFT JOIN y u ON y.i=u.i AND y.r<>u.r AND y.z LIKE u.z+'%' 
GROUP BY y.c;

LiveDemo

Uwaga: Jest to lista oddzielona przecinkami, a nie rzeczywista tablica. Ale główna idea jest taka sama jak w PostgreSQL.

EDYCJA 2:

Właściwie WITH ORDINALITYmożna go wymienić:

WITH y AS(SELECT *,ROW_NUMBER()OVER()r FROM t,LATERAL unnest(c)z)
SELECT y.c,EVERY(u.z IS NULL)
FROM y LEFT JOIN y u ON y.i=u.i AND y.r<>u.r AND y.z LIKE u.z||'%' GROUP BY y.c

SqlFiddleDemo

Brachylog , 8 bajtów

¬(⊇pa₀ᵈ)

Wypróbuj online!

Dane wyjściowe poprzez sukces / niepowodzenie predykatu. Ostatni prawdomówny test zajmuje więcej niż 60 sekund, ["111","010","000","1101","1010","1000","0111","0010","1011","0110","11001","00110","10011","11000","00111","10010"] ale szybko mija go z dodanym bajtem, który eliminuje wiele możliwości wcześniej niż program robi inaczej ( Ċprzed sprawdzeniem permutacji zamiast ᵈpo sprawdzeniu permutacji, aby ograniczyć długość podlisty do dwa).

¬(     )    It cannot be shown that
   p        a permutation of
  ⊇         a sublist of the input
      ᵈ     is a pair of values [A,B] such that
    a₀      A is a prefix of B.

Mniej trywialny 9-bajtowy warianty niż ¬(⊇Ċpa₀ᵈ)który prowadzony jest w rozsądnym czasie ¬(⊇o₁a₀ᵈ), ¬(⊇o↔a₀ᵈ)i ¬(⊇oa₀ᵈ¹).

Perl 6 , 24 bajtów

{.all.starts-with(.one)}

Wypróbuj online!

Wow, zaskakująco krótko, używając długiego wbudowanego.

Wyjaśnienie

{                      }  # Anonymous code block taking a list
 .all                     # Do all of the strings
     .starts-with(    )   # Start with
                  .one    # Only one other string (i.e. itself)

Rakieta, 70 bajtów

(λ(l)(andmap(λ(e)(not(ormap(curryr string-prefix? e)(remv e l))))l))

Python, 58 55 bajtów

lambda l:sum(0==a.find(b)for a in l for b in l)==len(l)

JavaScript (ES6), 52 54

Edytuj 2 bajty zapisane thx @ Neil

a=>!a.some((w,i)=>a.some((v,j)=>i-j&&!w.indexOf(v)))

Test

f=a=>!a.some((w,i)=>a.some((v,j)=>i-j&&!w.indexOf(v)))

O.textContent += 'OK: '+
[["Hello", "World"]                      
,["Code", "Golf", "Is", "Cool"]
,["1", "2", "3", "4", "5"]
,["This", "test", "case", "is", "true"]          
,["111", "010", "000", "1101", "1010", "1000", "0111", "0010", "1011", 
 "0110", "11001", "00110", "10011", "11000", "00111", "10010"]
].map(a=>f(a)) 

O.textContent += '\nKO: '+
[["4", "42"]                             
,["1", "2", "3", "34"]                   
,["This", "test", "case", "is", "false", "t"]
,["He", "said", "Hello"]
,["0", "00", "00001"]
,["Duplicate", "Duplicate", "Keys", "Keys"]
].map(a=>f(a))

<pre id=O></pre>

Mathematica 75 69 68 bajtów

Jak zwykle gadatliwy. Ale Martin B był w stanie zmniejszyć kod o 7 bajtów.

Metoda 1: Przechowywanie danych wyjściowych w Array

(68 bajtów)

f@a_:=!Or@@(Join@@Array[a~Drop~{#}~StringStartsQ~a[[#]]&,Length@a])

f@{"111", "010", "000", "1101", "1010", "1000", "0111", "0010", "1011", "0110", "11001", "00110", "10011", "11000", "00111", "10010"}

Prawdziwe

f@{"He", "said", "Hello"}

Fałszywe

Metoda 2: Przechowywanie danych wyjściowych w List

(69 bajtów)

f@a_:=!Or@@Flatten[a~Drop~{#}~StringStartsQ~a[[#]]&/@Range@Length@a]

Mathematica, 41 bajtów

!Or@@StringStartsQ@@@Reverse@Sort@#~Subsets~{2}&

APL (Dyalog Unicode) , 13 bajtów ^SBCS

-2 bajty:

≢=∘≢∘⍸∘.(⊃⍷)⍨

Wypróbuj online!

Wyjaśnienie:

≢=∘≢∘⍸∘.(⊃⍷)⍨  ⍝ Monadic function train
         ⍷     ⍝ "Find": Convert the right argument into a boolean vector,
               ⍝ where ones correspond to instances of the left argument
        ⊃     ⍝ Take the first item of the above vector (i.e., only prefixes)
     ∘.(  )⍨  ⍝ Commutative outer product: take the above function and apply
              ⍝ it for each possible pair of elements in the input
              ⍝ If the input is a prefix code, the above should have a number of ones
              ⍝ equal to the length of the input (i.e., each item is a prefix of only itself)
              ⍝ To test this...
     ⍸        ⍝ Find the location of all ones in the above
   ≢∘         ⍝ Take the length of the above
≢=∘           ⍝ Compare to the length of the input

J , 17 bajtów

#=1#.1#.{.@E.&>/~

Wypróbuj online!

Uwaga: faktycznie napisałem to przed spojrzeniem na odpowiedź APL, aby podejść do niej bez uprzedzeń. Okazuje się, że podejścia są prawie identyczne, co jest interesujące. Myślę, że to naturalne rozwiązanie typu „tablicowe myślenie”

Weź dane w ramce, ponieważ ciągi mają nierówną długość.

Utwórz tabelę funkcji /~dla każdego elementu sparowanego z każdym elementem i sprawdź, czy na początku jest dopasowanie {.@E.. To da macierz wyników 1-0.

Zsumuj to dwukrotnie 1#.1#. aby uzyskać pojedynczą liczbę reprezentującą „wszystkie w macierzy” i sprawdź, czy liczba ta jest taka sama jak długość danych wejściowych#= . Jeśli tak, to jedynymi dopasowaniami prefiksów są dopasowania własne, tzn. Mamy kod prefiksu.

rozwiązanie sortujące, 18 bajtów

0=1#.2{.@E.&>/\/:~

Próba innego podejścia. To rozwiązanie sortuje i sprawdza sąsiednie pary.

Wypróbuj online!

R , 48 bajtów

function(s)sum(outer(s,s,startsWith))==length(s)

Wypróbuj online!

Objaśnienie: outer(s,s,startsWith)wyświetla macierz logiki sprawdzającą, czy s[i]jest prefiksem s[j]. Jeśli sjest to kod przedrostka, to w wyniku tego są dokładnie length(s)PRAWDZIWE elementy, odpowiadające elementom ukośnym ( s[i]jest to sam przedrostek).

Pyth - 13 12 bajtów

!ssmm}d._k-Q

Wypróbuj online tutaj .

Rubinowy, 48 bajtów

Wykorzystuje argumenty jako dane wejściowe, a standardowe jako dane wyjściowe.

p !$*.map{a,*b=$*.rotate!
a.start_with? *b}.any?

Scala, 71 bajtów

(s:Seq[String])=>(for{x<-s;y<-s}yield x!=y&&x.startsWith(y)).forall(!_)

Rakieta 130 bajtów

(define g #t)(for((n(length l)))(for((i(length l))#:unless(= i n))(when(string-prefix?(list-ref l i)(list-ref l n))(set! g #f))))g

Nie golfowany:

(define(f l)
  (define g #t)
  (for ((n (length l)))
    (for ((i (length l)) #:unless (= i n))
      (when (string-prefix? (list-ref l i) (list-ref l n))
        (set! g #f))))g)

Testowanie:

(f [list "Hello" "World"])             
(f [list "Code" "Golf" "Is" "Cool"])
(f [list "1" "2" "3" "4" "5"])
(f [list "This" "test" "case" "is" "true"])          
(f [list "111" "010" "000" "1101" "1010" "1000" "0111" "0010" "1011" 
         "0110" "11001" "00110" "10011" "11000" "00111" "10010"])

(f [list "4" "42"])                             
(f [list "1" "2" "3" "34"])                   
(f [list "This" "test" "case" "is" "false" "t"])
(f [list "He" "said" "Hello"])
(f [list "0" "00" "00001"])
(f [list "Duplicate" "Duplicate" "Keys" "Keys"])

Wydajność:

#t
#t
#t
#t
#t
#f
#f
#f
#f
#f
#f

C (gcc) , 93 bajty

p(r,e,f,i,x)char**r;{for(f=i=0;i<e;++i)for(x=0;x<e;++x)f|=x!=i&&strstr(r[i],r[x])==r[i];r=f;}

Wypróbuj online!

Proste podwójne dla pętli za pomocą strstr(a,b)==ado sprawdzania prefektów. Dodane głównie, ponieważ wydaje się, że nie ma jeszcze odpowiedzi w języku C.

05AB1E , 13 bajtów

2.ÆDí«ε`Å?}O_

Za długo .. Początkowo miałem rozwiązanie 9-bajtowe, ale nie powiodło się w przypadku duplikatu testowego klucza.

Wypróbuj online lub sprawdź wszystkie przypadki testowe .

Wyjaśnienie:

2.Æ             # Get all combinations of two elements from the (implicit) input-list
   Dí           # Duplicate and reverse each pair
     «          # Merge the lists of pairs together
      ε         # Map each pair to:
       `        #  Push both strings to the stack
        Å?      #  And check if the first starts with the second
          }O    # After the map: sum to count all truthy values
            _   # And convert it to truthy if it's 0 or falsey if it's any other integer
                # (which is output implicitly as result)

Japt , 8 bajtów

á2 ËrbÃe

Spróbuj

á2 ËrbÃe     :Implicit input of array
á2           :Permutations of length 2
   Ë         :Map each pair
    r        :  Reduce by
     b       :  Get the index of the second in the first - 0 (falsey) if it's a prefix
      Ã      :End map
       e     :All truthy (-1 or >0)

C # (interaktywny kompilator Visual C #) , 70 bajtów

l=>!l.Any(x=>l.Where((y,i)=>l.IndexOf(x)!=i).Any(z=>z.StartsWith(x)));

Wypróbuj online!

Stax , 6 bajtów

å·↑↑¶Ω

Uruchom i debuguj

To powoduje powstanie niezerowej wartości dla prawdy.

Ogólna idea polega na rozważeniu każdej pary ciągów wejściowych. Jeśli indeks podciągu jednego w drugim jest zawsze równy zero, to nie jest to poprawny kod prefiksu. W stax daje indeks nieistniejącego substratu-1 . W ten sposób wszystkie wskaźniki parowania podciągów można pomnożyć razem.

Jest to ten sam algorytm, co rozwiązanie pyta isaacga, ale opracowałem go niezależnie.