Это код префикса?

33

В теории информации «префиксный код» - это словарь, в котором ни один из ключей не является префиксом другого. Другими словами, это означает, что ни одна из строк не начинается ни с одной другой.

Например, {"9", "55"}это код префикса, но {"5", "9", "55"}это не так.

Самым большим преимуществом этого является то, что закодированный текст может быть записан без разделителя между ними, и он все равно будет уникально дешифруемым. Это проявляется в алгоритмах сжатия, таких как кодирование Хаффмана , которое всегда генерирует оптимальный код префикса.

Ваша задача проста: по заданному списку строк определить, является ли он допустимым префиксным кодом.

Ваш вклад:

  • Будет список строк в любом разумном формате .

  • Будет содержать только печатаемые строки ASCII.

  • Не будет содержать пустых строк.

В результате вы получите значение true / falsey : Truthy, если это правильный код префикса, и false, если это не так.

Вот несколько настоящих тестов:

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

Вот несколько ложных тестовых случаев:

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

Это код-гольф, поэтому применяются стандартные лазейки, и выигрывает кратчайший ответ в байтах.

DJMcMayhem
источник
Вы хотите постоянное истинное значение или это может быть, например, «некоторое положительное целое число» (которое может варьироваться в зависимости от разных входных данных).
Мартин Эндер
@DrGreenEggsandHamDJ Я не думаю, что этот ответ предназначен для того, чтобы вообще касаться согласованности результатов, отсюда и вопрос. ;)
Мартин Эндер
Просто из любопытства. Задача гласит: «Самое большое преимущество этого заключается в том, что закодированный текст может быть записан без разделителя между ними, и он все равно будет уникально дешифруемым». Как что-то вроде бы 001быть уникально дешифруемым? Это может быть 00, 1или 0, 11.
Джоба
2
@ Joba Это зависит от того, какие у тебя ключи. Если у вас есть 0, 00, 1, 11все ключи, это не префикс-код, потому что 0 - префикс 00, а 1 - префикс 11. Код префикса - это то, где ни один из ключей не начинается с другого ключа. Так, например, если ваши ключи - 0, 10, 11это префиксный код и уникально дешифруемый. 001не является действительным сообщением, но 0011или 0010является уникально дешифруемым.
DJMcMayhem

Ответы:

11

Pyth, 8 байт

.AxM.PQ2

Тестирование

Возьмите все 2 элемента перестановки входных данных, сопоставьте каждую с индексом одной строки в другой (0 для префикса) и верните, все ли результаты верны (ненулевые).

isaacg
источник
12

Haskell, 37 байт

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

Каждый элемент xиз lповторяются один раз для каждого элемента , что это префикс, который ровно один раз для приставки свободного списка, давая первоначальный список. Свойство prefix проверяется путем сжатия обоих списков x, что обрезает элементы за пределами длины x.

XNOR
источник
Это элегантное решение (+1)
Майкл Кляйн
9

Java, 128 127 126 125 124 121 байт

(Спасибо, Кенни Лау, @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;}

Ungolfed

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

Выход

[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
Марв
источник
1
idk о java, но будет &работать вместо &&?
Maltysen
1
Хорошо, сохраняет еще один байт. В Java использование побитовых операторов с логическими операндами ведет себя так же, как нормальные логические операторы, за исключением того, что они не закорачивают, что в этом случае не требуется.
Март
Не могли бы вы просто изменить тип возвращаемого значения функции на intи вернуть 0и 1? Это сэкономило бы несколько байтов. Также я забываю, допустимо ли это в Java, но если вы объявите i, jи lво внешнем forцикле, который бы спас один байт от одной точки с запятой.
Патрик Робертс
@PatrickRoberts Maltysen предлагал это раньше, но это недопустимо в соответствии с наиболее одобренным определением истины / фальши . Поместить объявления в цикл, однако, вполне допустимо и довольно очевидно сейчас, когда я думаю об этом. Вот что вы получаете за игру в гольф в 4 часа утра: ^)
Marv
3
@Joba Довольно уверен, что это недопустимо, так как indexOf возвращает -1, когда строка не найдена; это должно быть indexOf(a[i])==0в этом случае нет сбережений.
Pokechu22
6

Python 2, 48 51 байт

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

Для каждого элемента aиз l, функция a.findнаходит индекс первого вхождения aво входной строке, давая -1для отсутствия. Итак, 0указывает префикс. В списке без префиксов отображение этой функции возвращает только один 0для aсебя. Функция проверяет, что это так для каждого a.


51 байт:

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

Замените ~символ с кодом ASCII 128 или выше.

Для каждого элемента aв l, копия включена для каждого элемента, который является его префиксом. Для списка без префиксов единственным таким элементом является aсам по себе, так что это дает исходный список.

XNOR
источник
4

CJam, 14 байтов

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

Тестирование.

объяснение

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.
Мартин Эндер
источник
4

JavaScript ES6, 65 43 40 байт

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

Мое предыдущее решение, которое обрабатывало строковые массивы всех символов UTF-8:

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

Мне удалось избежать, JSON.stringifyтак как задача определяет только печатные символы ASCII.

Тест

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>

Патрик Робертс
источник
3

Haskell, 49 байтов

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

Это имеет несколько частей:

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

Если два списка равны, то элемент является только префиксом самого себя, и он действителен.

Майкл Кляйн
источник
3

Сетчатка , 19 байт

Число байтов предполагает кодировку ISO 8859-1.

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

Входные данные должны быть разделены переводом строки. Вывод 0для фальши и 1правды.

Попробуйте онлайн! (Немного изменен для поддержки нескольких разделенных пробелами тестовых случаев вместо этого.)

объяснение

O`.+

Сортировка строк на входе. Если префикс существует, он окажется прямо перед строкой, которая его содержит.

Mm1`^(.+)¶\1

Попробуйте сопоставить ( M) полную строку, которая также находится в начале следующей строки. mАктивизирует многострочный режим таким образом, что ^матчи линии начала и 1гарантирует , что мы только рассчитывать на максимум один матч , так что выход 0или 1.

0

Чтобы поменять местами 0и 1в результате мы посчитаем количество 0с.

Мартин Эндер
источник
3

Java, 97 байт

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

Использует большинство приемов, найденных в ответе @ Marv , но также использует цикл foreach и равенство ссылок на строки.

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

Обратите внимание, что, как я уже сказал, здесь используется равенство строк. Это означает, что код может вести себя странно из-за интернирования String . Код работает при использовании аргументов, переданных из командной строки, а также при использовании чего-то, считываемого из командной строки. Если вы хотите жестко закодировать значения для тестирования, вам нужно вручную вызвать конструктор String, чтобы интернирование не происходило:

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")}));
Pokechu22
источник
@ Джо Кинг Смотрите вторую половину моего ответа; это немного сложно и зависит от того, как указан вход. Я даже не помню, как это писал
Pokechu22
3

PostgreSQL, 186 , 173 байта

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

Выход:

введите описание изображения здесь

На этот раз нет живой демо. http://sqlfiddle.com поддерживает только 9.3 и для запуска этой демонстрации 9.4 требуется.

Как это работает:

  1. Разбить массив строк с номером и назвать его y
  2. Получить все у
  3. LEFT OUTER JOINк той же производной таблице, основанной на том же i(id), но с другим, oridinalкоторые начинаются с префиксаy.z LIKE u.z||'%'
  4. Группировать результат на основе c(начальный массив) и использовать EVERYфункцию группировки. Если каждая строка из второй таблицы IS NULLозначает, что префиксов нет.

Введите, если кому-то интересно:

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

РЕДАКТИРОВАТЬ:

SQL Server 2016+ реализация:

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

Примечание. Это список, разделенный запятыми, а не реальный массив. Но основная идея такая же, как в PostgreSQL.


РЕДАКТИРОВАТЬ 2:

На самом деле WITH ORDINALITYможно заменить:

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

lad2025
источник
3

Брахилог , 8 байт

¬(⊇pa₀ᵈ)

Попробуйте онлайн!

Выходы через предикат успеха / неудачи. Занимает более 60 секунд в последнем достоверном тестовом примере, ["111","010","000","1101","1010","1000","0111","0010","1011","0110","11001","00110","10011","11000","00111","10010"] но быстро передает его с добавленным байтом, который исключает большое количество возможностей раньше, чем программа делает иначе ( Ċперед проверкой перестановок, а не после проверок перестановок, чтобы ограничить длину подсписка до два).

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

Менее тривиальные 9 байт вариантов , чем ¬(⊇Ċpa₀ᵈ)которые выполняются в разумных сроках являются ¬(⊇o₁a₀ᵈ), ¬(⊇o↔a₀ᵈ)и ¬(⊇oa₀ᵈ¹).

Несвязанная строка
источник
Если бы в этом вызове вместо «правдивости / ложности» использовались «два разных и непротиворечивых значения», это заняло бы всего 5 байтов.
Несвязанная строка
2

Perl 6 , 24 байта

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

Попробуйте онлайн!

Вау, на удивление коротко при использовании длинного встроенного.

объяснение

{                      }  # Anonymous code block taking a list
 .all                     # Do all of the strings
     .starts-with(    )   # Start with
                  .one    # Only one other string (i.e. itself)
Джо Кинг
источник
Я написал 50-байтовый ответ, но ваш только что выкинул мой из воды.
BB94
1
@ bb94 Да, я начал с аналогичного ответа, но столкнулся с той же проблемой, что и вы, с наборами с дублированными ключами, возвращающими правду. Написание этого ответа было невероятно удовлетворительным
Джо Кинг
1

Ракетка, 70 байт

(λ(l)(andmap(λ(e)(not(ormap(curryr string-prefix? e)(remv e l))))l))
Winny
источник
1

Python, 58 55 байт

lambda l:sum(0==a.find(b)for a in l for b in l)==len(l)
DJMcMayhem
источник
a.index(b)==0немного короче. В качестве альтернативы, вы могли бы сделать 0**sum(a.index(b)for a in l for b in l).
Мего
@Mego Это не работает, потому что indexвыдает исключение, когда bне найдено. А потому что так и должно быть ==, нет >=. Однако findработает. (И это тоже короче!)
DJMcMayhem
Ой, я хотел напечатать find. Сонный мозг сонный. Вторая версия также должна работать find.
Mego
@Mego Я не уверен, что получу вторую версию. Разве это не всегда возвращает 0?
DJMcMayhem
@Mego Это работает, только если каждая строка одинакова. Причина, по которой мы сравниваем его, len(l)заключается в том, что, поскольку мы перебираем все bs для каждого a, всегда будет хотя бы одно совпадение для каждого a. Поэтому мы проверяем, совпадает ли количество совпадений с количеством элементов.
DJMcMayhem
1

JavaScript (ES6), 52 54

Редактирование 2 байт сохраненного ТНХ @Neil

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

Тест

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>

edc65
источник
!w.indexOf(v)?
Нейл
@ Нейл, спасибо
edc65
1

Mathematica 75 69 68 байт

Болтливый как обычно. Но Мартин Б смог уменьшить код на 7 байтов.

Метод 1: Сохранение вывода в Array

(68 байт)

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

Правда


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

Ложь


Метод 2: Сохранение вывода в List

(69 байт)

f@a_:=!Or@@Flatten[a~Drop~{#}~StringStartsQ~a[[#]]&/@Range@Length@a]
DavidC
источник
Правила приоритета должны заставить a~Drop~{#}~StringStartsQ~a[[#]]работать. Также Arrayследует сохранить несколько байтов Length, особенно потому, что это позволит вам использовать Join@@вместо Flatten@(при условии, что вы используете Flattenтолько для одного уровня).
Мартин Эндер
Спасибо за предложение. Я посмотрю Arrayпозже.
DavidC
1

Mathematica, 41 байт

!Or@@StringStartsQ@@@Reverse@Sort@#~Subsets~{2}&
Симмонс
источник
1

APL (Dyalog Unicode) , 13 байтов SBCS

-2 байта:

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

Попробуйте онлайн!

Объяснение:

≢=∘≢∘⍸∘.(⊃⍷)⍨   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
voidhawk
источник
~2∊+\⊃¨∘.⍷⍨⎕­
НГН
1

J , 17 байт

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

Попробуйте онлайн!

Примечание: я действительно написал это, прежде чем посмотреть на ответ APL, чтобы подойти к нему без предвзятости. Оказывается, подходы практически идентичны, что интересно. Я думаю, что это естественное решение для "массива мышления"

Возьмите вход в штучной упаковке, потому что строки имеют неравную длину.

Создайте таблицу функций /~каждого элемента в паре с каждым элементом и посмотрите, есть ли совпадение в начале {.@E.. Это даст матрицу результатов 1-0.

Суммируйте его дважды, 1#.1#.чтобы получить одно число, представляющее «все единицы в матрице», и посмотрите, совпадает ли это число с длиной ввода #=. Если это так, то единственным совпадением префикса являются сам совпадения, т. Е. У нас есть код префикса.

сортировочное решение, 18 байт

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

Попытка при другом подходе. Это решение сортирует и смотрит на соседние пары.

Попробуйте онлайн!

Ион
источник
1

R , 48 байт

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

Попробуйте онлайн!

Объяснение: outer(s,s,startsWith)выводит матрицу логики, проверяющую, s[i]является ли префикс s[j]. Если sэто префиксный код, то в результате есть ровно length(s)ИСТИННЫЕ элементы, соответствующие диагональным элементам ( s[i]сам по себе является префиксом).

Робин Райдер
источник
1
Я нашел кучу других 48-байтовых альтернатив, например, function(s)all(colSums(outer(s,s,startsWith))<2)но это startsWithфункция, о которой я не знал! Хорошая находка.
Джузеппе
1
@Giuseppe Я попробовал несколько способов проверить, является ли матрица единичной матрицей, но также не смог получить ее под 48 байтами. Я думал, что этот способ легче всего понять, но я уверен, что кто-то с этим справится!
Робин Райдер
47 байтов путем инвертирования TRUEи FALSE...
Джузеппе
@ Giuseppe Это разрешено? Правила явно запрашивают правдивость, когда ввод является действительным префиксным кодом. (Также ваша ссылка на 48-байтовую версию, но я предполагаю, что ваше предложение заменить == на >. :-))
Робин Райдер
0

Рубин, 48 байтов

Использует аргументы в качестве входных данных и стандартный вывод в качестве выходных.

p !$*.map{a,*b=$*.rotate!
a.start_with? *b}.any?
ezrast
источник
0

Скала, 71 байт

(s:Seq[String])=>(for{x<-s;y<-s}yield x!=y&&x.startsWith(y)).forall(!_)
Иаков
источник
0

Ракетка 130 байт

(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

Ungolfed:

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

Тестирование:

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

Выход:

#t
#t
#t
#t
#t
#f
#f
#f
#f
#f
#f
rnso
источник
0

C (gcc) , 93 байта

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

Попробуйте онлайн!

Простое двойное использование цикла strstr(a,b)==aдля проверки предпочтений. В основном добавлено, поскольку пока не существует ответа C.

LambdaBeta
источник
88 байт
floorcat
0

05AB1E , 13 байтов

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

Слишком долго. Изначально у меня было 9-байтовое решение, но в тестовом случае с дублированным ключом оно не удалось.

Попробуйте онлайн или проверьте все контрольные примеры .

Объяснение:

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)
Кевин Круйссен
источник
0

Japt , 8 байт

á2 ËrbÃe

Попытайся

á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)
мохнатый
источник
0

Stax , 6 байт

å·↑↑¶Ω

Запустите и отладьте его

Это производит ненулевой для правды.

Общая идея заключается в рассмотрении каждой пары строк на входе. Если индекс подстроки одного в другом всегда равен нулю, то это неверный префиксный код. В stax возвращается индекс несуществующей подстроки -1. Таким образом, все индексы парных подстрок могут быть умножены вместе.

Это тот же алгоритм, что и в pyth-решении Исаака, но я разработал его независимо.

рекурсивный
источник