Substring Pengidentifikasi Unik Terpendek

23

Diberikan daftar string, ganti setiap string dengan salah satu substring yang tidak kosong yang bukan substring dari string lain dalam daftar dan sesingkat mungkin.

Contoh

Diberikan daftar ["hello","hallo","hola"], "hello"harus diganti hanya "e"karena substring ini tidak terkandung dalam "hallo"dan "hola"dan sesingkat mungkin. "hallo"dapat diganti dengan baik "ha"atau "al"dan "hola"oleh salah "ho", "ol"atau "la".

Aturan

  • Anda dapat mengasumsikan bahwa string tidak akan kosong dan hanya berisi karakter alfabet dari kasus yang sama.
  • Anda dapat mengasumsikan bahwa substring seperti itu ada untuk setiap string dalam daftar, yaitu tidak ada string dalam daftar yang akan menjadi substring dari salah satu string lainnya.
  • Input dan output dapat dalam format apa pun yang masuk akal.
  • Ini adalah , jadi coba gunakan sesedikit mungkin byte dalam bahasa pilihan Anda.

Uji Kasus

Hanya satu output yang mungkin diberikan untuk sebagian besar kasus.

["ppcg"] -> ["p"] (or ["c"] or ["g"])
["hello","hallo","hola"] -> ["e","ha","ho"]
["abc","bca","bac"] -> ["ab","ca","ba"]
["abc","abd","dbc"] -> ["abc","bd","db"]
["lorem","ipsum","dolor","sit","amet"] -> ["re","p","d","si","a"]
["abc","acb","bac","bca","cab","cba"] -> ["abc","acb","bac","bca","cab","cba"]

Terkait: Substring Identifikasi Terpendek - ide serupa, tetapi lebih banyak melibatkan aturan dan format rumit.

Laikoni
sumber
Mengapa isnt ""(string kosong) secara unik mengidentifikasi untuk "ppcg"case tunggal ?
MooseBoys
2
@ MooseBoys Diberikan daftar string, ganti setiap string dengan salah satu dari substring yang tidak kosong
Tn. Xcoder

Jawaban:

4

Python 2 , 116 byte

def f(a):g=lambda s,S:s not in`set(a)-{S}`[3:]and min(s,g(s[1:],S),g(s[:-1],S),key=len)or S;return[g(s,s)for s in a]

Cobalah online!

Chas Brown
sumber
4

Pyth , 12 byte

mhf!ts}LTQ.:

Coba di sini!

Bagaimana itu bekerja

Pada dasarnya filter substring dari masing-masing yang hanya terjadi di salah satu string dalam daftar (yaitu, itu unik untuk string itu) dan mendapatkan yang pertama.

mhf!ts}LTQ.:     Full program, Q=eval(stdin_input())
m         .:     Map over Q and obtain all the substrings of each.
  f              And filter-keep those that satisfy (var: T)...
      }LTQ       ... For each string in Q, yield 1 if it contains T, else 0.
   !ts           ... Sum the list, decrement and negate. 
 h               Head. Yields the first valid substring, which is always the shortest.
Tuan Xcoder
sumber
4

Prolog (SWI) , 175 163 byte

S/L/R:-sub_string(S,_,L,_,R).
[H|T]+[I|R]:-string_length(H,L),between(1,L,X),H/X/I,T+R.
R+R.
L-R:-L+R,forall(member(E,L),findall(_,(member(F,R),\+ \+ E/_/F),[_])).

Cobalah online!

Sebagian besar hal di sini seharusnya cukup jelas, tetapi:

Penjelasan

Tanda tangan: ( += input, ?= opsional, -= output, := ekspresi)

  • sub_string(+String, ?Before, ?Length, ?After, ?SubString)
  • string_length(+String, -Length)
  • member(?Elem, ?List)
  • between(+Low, +High, ?Value)
  • findall(+Template, :Goal, -Bag)
  • forall(:Cond, :Action)

\+ \+hanya not not(yaitu mengonversi kecocokan ke boolean (dalam hal ini, mencegah kecocokan keduanya psecara ppcgterpisah))

Khusus ASCII
sumber
Alat yang tepat untuk pekerjaan itu: P kecuali fakta bahwa itu sangat mengesankan
ASCII-only
4

J , 30 29 25 byte

1(|:(0{-.&,)"_1]\.)<\\.&>

Cobalah online!

                   <\\.&>        a 3-dimensional array of substrings
1 |:                             transpose each matrix to sort the substrings by length
1              ]\.               all choices where one word is missing
    (0{-.&,)"_1                  for every matrix, flatten, remove substrings
                                  that are present in the corresponding complement,
                                  pick first
FrownyFrog
sumber
3

JavaScript (ES6), 93 byte

a=>a.map(s=>(L=s.length,g=n=>a.every(S=>S==s|!~S.search(u=s.substr(n%L,n/L+1)))?u:g(n+1))(0))

Cobalah online!

Bagaimana?

Untuk setiap string dengan panjang L dalam array input a [] dan dimulai dengan n = 0 , kami menggunakan fungsi rekursif g () untuk menghasilkan semua substring u dari s dengan:

u = s.substr(n % L, n / L + 1)

Misalnya, dengan s = "abc" dan L = 3 :

 n | n%L | floor(n/L+1) | u
---+-----+--------------+-------
 0 |  0  |       1      | "a"
 1 |  1  |       1      | "b"
 2 |  2  |       1      | "c"
 3 |  0  |       2      | "ab"
 4 |  1  |       2      | "bc"
 5 |  2  |       2      | "c"
 6 |  0  |       3      | "abc"
 7 |  1  |       3      | "bc"
 8 |  2  |       3      | "c"

Beberapa substring dihasilkan beberapa kali, tetapi tidak masalah. Yang penting adalah bahwa semua substring dengan panjang N telah dihasilkan sebelum substring dengan panjang N + 1 .

Kami menghentikan proses secepat u tidak dapat ditemukan di setiap lain String S di sebuah [] , yang dijamin terjadi ketika u == s dalam kasus terburuk, sesuai tantangan aturan # 2:

tidak ada string dalam daftar yang akan menjadi substring dari string lainnya

Oleh karena itu, dalam contoh di atas, langkah 7 dan 8 sebenarnya tidak akan pernah diproses.

Arnauld
sumber
2

PowerShell , 107 byte

($a=$args)|%{$(for($i=0;$i++-lt($g=($s=$_)|% Le*)){0..($g-$i)|%{$s|% s*g $_ $i}|?{!($a-match$_-ne$s)}})[0]}

Cobalah online!

Penjelasan

Untuk setiap string yang disediakan (dan tetapkan seluruh array $a):

  • Lakukan forpengulangan pada setiap panjang substring (berdasarkan 1) dari string (menugaskan string itu sendiri $sdan panjangnya $g)
  • Untuk setiap panjang ( $i):
    • Buat loop indeks, dari 0 hingga panjang - $i, lalu untuk setiap indeks:
      • Dapatkan substring dari string saat ini ( $s) di posisi $_(indeks) dan panjangnya$i
      • Berikan substring itu ke Where-Object( ?), dan kembalikan jika:
        • Subset dari array ( $a) yang tidak mengandung string saat ini $s, tidak memiliki kecocokan untuk substring saat ini$_

Kembali pada level string, kita memiliki semua substring dari string ini yang tidak ditemukan pada yang lain, jadi ambil yang pertama [0]karena kita hanya membutuhkan satu dari mereka, kemudian lanjutkan dengan string berikutnya.

briantis
sumber
0

C # (Visual C # Interactive Compiler) , 149 byte

a=>a.Select(s=>{var t=s;for(int j=0,k,l=s.Length;j++<l;)for(k=-1;j+k++<l;)if(!a.Where(u=>s!=u&u.Contains(t=s.Substring(k,j))).Any())j=k=l;return t;})

Cobalah online!

Kurang bermain golf ...

// a is an input array of strings
a=>
  // iterate over input array   
  a.Select(s=>{
    // t is the result string
    var t=s;
    // j is the substring length
    for(int j=0,k,l=s.Length;j++<l;)
      // k is the start index
      for(k=-1;j+k++<l;)
        // LINQ query to check if substring is valid
        // the tested string is collected in t
        if(!a.Where(u=>s!=u&u.Contains(t=s.Substring(k,j))).Any())
          // break loops
          j=k=l;
    // return result
    return t;
  })
dana
sumber