En teoría de la información, un "código de prefijo" es un diccionario donde ninguna de las claves es prefijo de otra. En otras palabras, esto significa que ninguna de las cadenas comienza con ninguna de las otras.

Por ejemplo, {"9", "55"}es un código de prefijo, pero {"5", "9", "55"}no lo es.

La mayor ventaja de esto es que el texto codificado se puede escribir sin separador entre ellos, y seguirá siendo descifrable de forma única. Esto se muestra en algoritmos de compresión como la codificación Huffman , que siempre genera el código de prefijo óptimo.

Su tarea es simple: dada una lista de cadenas, determine si es o no un código de prefijo válido.

Tu aportación:

• Será una lista de cadenas en cualquier formato razonable .

• Solo contendrá cadenas ASCII imprimibles.

• No contendrá cadenas vacías.

Su salida será un valor verdadero / falso : Verdad si es un código de prefijo válido, y falso si no lo es.

Aquí hay algunos casos de prueba verdaderos:

["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"]

Aquí hay algunos casos de prueba falsos:

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

Este es el código de golf, por lo que se aplican las lagunas estándar y gana la respuesta más corta en bytes.

Pyth, 8 bytes

.AxM.PQ2

Banco de pruebas

Tome todas las permutaciones de 2 elementos de la entrada, asigne cada una al índice de una cadena en la otra (0 para un prefijo) y devuelva si todos los resultados son verdaderos (distintos de cero).

Haskell, 37 bytes

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

Cada elemento xde lse repite una vez para cada elemento del que es un prefijo, que es exactamente una vez para una lista sin prefijo, dando la lista original. La propiedad del prefijo se comprime comprimiendo ambas listas con x, lo que corta elementos más allá de la longitud de x.

Java, 128 127 126 125 124 121 bytes

(Gracias @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;}

Sin golf

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

Salida

[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 bytes

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

Para cada elemento ade l, la función a.findencuentra el índice de la primera aparición de aen la cadena de entrada, dando -1una ausencia. Entonces, 0indica un prefijo. En una lista libre de prefijo, la cartografía de esta función devuelve sólo un único 0por así mismo. La función verifica que este sea el caso para todos a.

51 bytes:

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

Reemplace ~con un carácter con código ASCII 128 o superior.

Para cada elemento aen l, se incluye una copia para cada elemento que es un prefijo del mismo. Para una lista libre de prefijos, el único elemento de este tipo es él amismo, por lo que se obtiene la lista original.

CJam, 14 bytes

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

Banco de pruebas.

Explicación

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 bytes

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

Mi solución anterior, que manejaba matrices de cadenas de todos los caracteres UTF-8:

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

Pude evitarlo JSON.stringifyya que el desafío especifica solo caracteres ASCII imprimibles.

Prueba

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 bytes

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

Esto tiene un par de partes:

-- 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)

Si las dos listas son iguales, entonces un elemento es solo el prefijo de sí mismo y es válido.

Retina , 19 bytes

El recuento de bytes asume la codificación ISO 8859-1.

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

La entrada debe estar separada por salto de línea. La salida es 0por falsedad y 1por verdad.

Pruébalo en línea! (Ligeramente modificado para admitir múltiples casos de prueba separados por espacios).

Explicación

O`.+

Ordenar las líneas en la entrada. Si existe un prefijo, terminará directamente frente a una cadena que lo contiene.

Mm1`^(.+)¶\1

Intente hacer coincidir ( M) una línea completa que también se encuentra al comienzo de la siguiente línea. La mactiva modo multilínea de tal manera que ^los comienzos partidos de línea y los 1asegura que sólo cuentan como máximo un partido de tal manera que la salida es 0o 1.

0

Para intercambiar 0y 1en el resultado, contamos el número de 0s.

Java, 97 bytes

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

Utiliza la mayoría de los trucos que se encuentran en la respuesta de @ Marv , pero también hace uso del bucle foreach y la igualdad de referencia de cadena.

No minificado:

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

Tenga en cuenta que, como dije, esto usa la igualdad de referencia de cadena. Eso significa que el código puede comportarse de manera extraña debido a la internación de String . El código funciona cuando se usan argumentos pasados ​​desde la línea de comandos, y también cuando se usa algo leído desde la línea de comandos. Sin embargo, si desea codificar los valores para probar, deberá llamar manualmente al constructor de cadenas para forzar que no ocurra la internación:

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 bytes

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

Salida:

No hay demostración en vivo esta vez. http://sqlfiddle.com solo admite 9.3 y para ejecutar esta demostración se requiere 9.4.

Cómo funciona:

1. Separe la matriz de cadenas con un número y asígnele un nombre y
2. Obtén todo y
3. LEFT OUTER JOINa la misma tabla derivada basada en el mismo i(id), pero con diferentes oridinalque comienzan con el prefijoy.z LIKE u.z||'%'
4. Agrupe el resultado basado en c(matriz inicial) y use la EVERYfunción de agrupación Si cada fila de la segunda tabla IS NULLsignifica que no hay prefijos.

Ingrese si alguien está interesado:

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

EDITAR:

SQL Server 2016+ implementación:

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

Nota: es una lista separada por comas, no una matriz real. Pero la idea principal es la misma que en PostgreSQL.

EDITAR 2:

En realidad WITH ORDINALITYpodría ser reemplazado:

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 bytes

¬(⊇pa₀ᵈ)

Pruébalo en línea!

Salidas a través del predicado éxito / fracaso. Lleva más de 60 segundos en el último caso de prueba de verdad, ["111","010","000","1101","1010","1000","0111","0010","1011","0110","11001","00110","10011","11000","00111","10010"] pero lo pasa rápidamente con un byte agregado que elimina una gran cantidad de posibilidades antes de lo que el programa hace de otra manera ( Ċantes de verificar las permutaciones en lugar de ᵈdespués de verificar las permutaciones, para limitar la longitud de la sublista a dos).

¬(     )    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.

Menos trivial 9 bytes de variantes ¬(⊇Ċpa₀ᵈ)que se ejecutan en un tiempo razonable son ¬(⊇o₁a₀ᵈ), ¬(⊇o↔a₀ᵈ)y ¬(⊇oa₀ᵈ¹).

Perl 6 , 24 bytes

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

Pruébalo en línea!

Wow, sorprendentemente corto mientras usa un largo incorporado.

Explicación

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

Raqueta, 70 bytes

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

Python, 58 55 bytes

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

JavaScript (ES6), 52 54

Editar 2 bytes guardados gracias a @Neil

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

Prueba

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 bytes

Locuaz como siempre. Pero Martin B pudo reducir el código en 7 bytes.

Método 1: almacenamiento de salida en un Array

(68 bytes)

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

Cierto

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

Falso

Método 2: almacenamiento de salida en un List

(69 bytes)

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

Mathematica, 41 bytes

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

APL (Dyalog Unicode) , ^{SBCS de} 13 bytes

-2 bytes:

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

Pruébalo en línea!

Explicación:

≢=∘≢∘⍸∘.(⊃⍷)⍨  ⍝ 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 bytes

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

Pruébalo en línea!

Nota: en realidad escribí esto antes de mirar la respuesta APL, para abordarla sin sesgos. Resulta que los enfoques son casi idénticos, lo cual es interesante. Supongo que esta es la solución natural "array thinknig"

Tome la entrada en recuadro porque las cadenas son de longitud desigual.

Cree una tabla /~de funciones propias de cada elemento emparejado con cada elemento y vea si hay una coincidencia al comienzo {.@E.. Esto producirá una matriz de resultados 1-0.

Suma dos veces 1#.1#.para obtener un número único que represente "todos los de la matriz", y ve si ese número es igual a la longitud de la entrada #=. Si es así, las únicas coincidencias de prefijo son coincidencias propias, es decir, tenemos un código de prefijo.

solución de clasificación, 18 bytes

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

Intento de un enfoque diferente. Esta solución clasifica y mira los pares adyacentes.

Pruébalo en línea!

R , 48 bytes

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

Pruébalo en línea!

Explicación: outer(s,s,startsWith)genera una matriz de lógicos que verifica si s[i]es un prefijo de s[j]. Si ses un código de prefijo, entonces hay exactamente length(s)elementos VERDADEROS en el resultado, correspondientes a los elementos diagonales ( s[i]es un prefijo de sí mismo).

Pyth - 13 12 bytes

!ssmm}d._k-Q

Pruébelo en línea aquí .

Ruby, 48 bytes

Utiliza argumentos como entrada y stdout como salida.

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

Scala, 71 bytes

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

Raqueta 130 bytes

(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

Sin golf:

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

Pruebas:

(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"])

Salida:

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

C (gcc) , 93 bytes

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

Pruébalo en línea!

Simple doble para el bucle que usa strstr(a,b)==apara verificar las premisas. Principalmente agregado ya que todavía no parece haber una respuesta C.

05AB1E , 13 bytes

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

Demasiado tiempo. Inicialmente tenía una solución de 9 bytes, pero falló para el caso de prueba de clave duplicada.

Pruébelo en línea o verifique todos los casos de prueba .

Explicación:

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 bytes

á2 ËrbÃe

Intentalo

á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 # (compilador interactivo de Visual C #) , 70 bytes

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

Pruébalo en línea!

Stax , 6 bytes

å·↑↑¶Ω

Ejecutar y depurarlo

Esto produce no cero para la verdad.

La idea general es considerar cada par de cadenas en la entrada. Si el índice de subcadena de uno en el otro es siempre cero, entonces no es un código de prefijo válido. En stax, el índice de rendimientos de una subcadena no existente-1 . De esta manera, todos los índices de subcadenas por pares se pueden multiplicar juntos.

Este es el mismo algoritmo que la solución pyth de Isaac, pero lo desarrollé de forma independiente.