Given this list of all the words in english and a string with s_me missi_g lett__s, find one way to fill in the letters. Do note that some words on the list contain special characters (! & ' , - . /) and numbers


This list and a string with missing letters.

The input sentence can contain or be missing any of these characters: ! & ' , - . / 0 1 2 3 4 5 6 7 8 9 A B C D E F G H I J K L M N O P Q R S T U V W X Y Z a b c d e f g h i j k l m n o p q r s t u v w x y z. An underscore is used to mark a missing character. All missing characters have a possible solution.


One possible solution with all the missing letters fixed. Words split at a space . Case sensitive, includes words with ! & ' , - . /

Test Cases

Input: a string with s_me missi_g lett__s

All possible outputs: a string with [same, seme, sime, some] missing letters

Output Example: a string with same missing letters

Input: A_ 6-po_nt A/_ ada__er

All possible outputs: [A., A1, A4, A5, AA, AB, AF, AG, AH, AI, AY, AJ, AK, AM, AO, AP, AQ, AS, AT, AU, AV, AW, Ax, AZ] 6-point [A/C, A/F, A/O, A/P, A/V]

Output Example: A. 6-point A/C adapter

Input: A_M AT&_ platform_s scyth_'s hee_hee_ he-_e! 2_4,5_t

All possible outputs: [A&M, AAM, ABM, ACM, ADM, AFM, AGM, AIM, ALM, APM, ARM, ASM, ATM, AUM, AVM] AT&T platform's scythe's hee-hee! he-he! 2,4,5.t

Output example: A&M AT&T platform's scythe's hee-hee! he-he! 2,4,5-t

SemicolonSeperatedValue for first possible output:

a string with s_me missi_g lett__s;a string with same missing letters
A_ 6-po_nt A/_ ada__er;A. 6-point A/C adapter
A_M AT&_ platform_s scyth_'s hee_hee_ he-_e! 2_4,5_t;A&M AT&T platform's scythe's hee-hee! he-he! 2,4,5-t


As this is , shortest solution in bytes wins.

  • 1
    \$\begingroup\$ I tried to made this really clear and well defined unlike the other similar questions, what about it is unclear? \$\endgroup\$ – pfg May 14 '18 at 18:51
  • 1
    \$\begingroup\$ @pfg how flexible is the input / output? can we work with a list of the words? \$\endgroup\$ – Rod May 14 '18 at 19:11
  • 3
    \$\begingroup\$ For test case purposes, can we have the 'words' list be /usr/share/dict/words instead of something on the web? letters, for example, is not in the standard unix words file (although letter is). That way, on TIO you can use the local file. \$\endgroup\$ – Chas Brown May 14 '18 at 19:13
  • \$\begingroup\$ @pfg i meant the 'Words split at a space' part, the input/output can be separated words? Or we need to split / join the space? \$\endgroup\$ – Rod May 14 '18 at 19:16
  • 3
    \$\begingroup\$ @pfg: TIO code is running on a virtual unix instance; so in python (for example) I can use f=open('/usr/share/dict/words');W=f.read() to access that standard unix file. \$\endgroup\$ – Chas Brown May 14 '18 at 19:29

Python 2, 96 105 99 101 bytes

lambda p,W:' '.join([w for w in W if all(map(lambda c,d:c in['_',d]and d,s,w))][0]for s in p.split())

Try it online!

W is the list of words which is set up separately; I'm using the unix words file on TIO, which doesn't contain platform's or scythes's.

Added 2 bytes for Shaggy.

  • 2
    \$\begingroup\$ The spec requires you to take the provided dictionary as input. It looks like you're using a different dictionary and assuming it's assigned to a predefined variable. \$\endgroup\$ – Shaggy May 14 '18 at 22:42

C (gcc), 232 bytes

Like the other submissions, I used /usr/share/dict/words; change the first argument to select another wordlist and the second argument to specify the size (the function itself just needs an array of strings as the dictionary.) On a non-matched word with a _, the original word is returned.

char*g(s,t,u,v,w)char*s,**t,*u,*v,*w;{for(w=strchr(s,95)?0:s;(v=*t++)&&!w;w=(*u+*v)?0:*(t-1))for(u=s;*u&&*v&&*v==*(*u==95?v:u);u++,v++);return w?w:s;}h(s,t,c,u)char*s,**t,*c,*u;{for(u=s;c=strtok(u," ");u=0)printf(" %s"+!!u,g(c,t));}

Try it online!

  • \$\begingroup\$ 211 bytes *g(s,t,u,v,w)char*s,**t,*u,*v,*w;{for(w=index(s,95)?0:s;(v=*t)&&!w;w=*u+*v?0:*t,t++)for(u=s;!(*u-95&&*v-*u)&&*v++&&*u++;);s=w?w:s;}h(s,t,c,u)int*s,*t,*c,*u;{for(u=s;c=strtok(u," ");u=0)printf(" %s"+!!u,g(c,t));} \$\endgroup\$ – ceilingcat Jun 26 '18 at 22:16

Java 10, 127 bytes

L->s->{for(var x:s.split(" "))for(var w:L)if(w.matches(x.replace(".","\\.").replace("_","."))){System.out.print(w+" ");break;}}

Try it online (also uses the /usr/share/dict/words TIO word-library, which doesn't contain platform's or scyth's, but the lambda-function works with any kind of list String-List provided).


L->s->{                   // Method with String-List & String parameters and no return-type
  for(var x:s.split(" ")) //  Loop over the parts of the input-String, split by spaces
    for(var w:L)          //   Inner loop over the words
                          //    Escape all dots
                          //    Replace all underscores with regex-dots
                          //    And if the current word matches it:
        System.out.print(w+" ");
                          //     Print the word, plus a space
        break;}}          //     And stop the inner loop

Jelly,  18  25 bytes

...noticed a bug during write-up, cost 7 to fix naively. There must be better!


A dyadic link accepting a list of lists of characters on the left (words) and a list of characters on the right (string) which returns a lists of characters.

Try it online!
...using a hugely restricted word list due to incredible inefficiency (although it could be far worse!)


This is the 18-byte code...

ṗ⁹ḲL¤K€œ&⁼⁹ḟ”_¤ɗƇḢ - Link: words, W; string, S
    ¤              - nilad followed by link(s) as a nilad:
 ⁹                 -   chain's right argument (S)
  Ḳ                -   split on spaces
   L               -   length
ṗ                  - Cartesian power (all ways of making that number of words)
     K€            - join €ach with spaces
                Ƈ  - filter keep those for which:
               ɗ   -   last three links as a dyad:
       œ&          -   multi-set intersection
              ¤    -   nilad followed by link(s) as a nilad:
          ⁹        -     chain's right argument (S)
            ”_     -     literal '_' character
           ḟ       -     filter discard
         ⁼         -   equal? (multi-set intersection == string without '_'s?)
                 Ḣ - head (first result) ... UGH BUG.

...the current fix is to filter the list to only keep those with a length equal to the input before heading:

...⁹,L€EɗƇḢ - (continued)
   ⁹        - use the chain's right argument as the right
            -   argument of the first 17 bytes of the code above.
         Ƈ  - filter keep those for which:
        ɗ   -   last three links as a dyad:
    ,       -   pair left and right
     L€     -   length of €ach
       E    -   equal?
          Ḣ - head

Clean, 174 171 bytes

import StdEnv,Text
$l=join" "o map(hd o filter(\w=any((==)w)l)o@o split"_")o split" "
@[h:t]|t>[]=[h<+c<+v\\c<-['0'..'9']++['a'..'z']++['A'..'Z']++['!&\',-./'],v<- @t]=[h]

Try it online!

TIO link uses the dictionary in /usr/share/dict/words but it'll work with any list of words.

  • \$\begingroup\$ I'm pretty sure it's possible to turn the @ helper into a fold, so if anyone has any ideas about that it'd be wonderful. \$\endgroup\$ – Οurous May 14 '18 at 23:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.