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, 2018 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, 2018 at 19:11
  • 4
    \$\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, 2018 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, 2018 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, 2018 at 19:29

8 Answers 8


Jelly,  18 25 20  19 bytes

...noticed a bug during write-up, cost 7 to fix naively, then saved 5 with another approach to fix it.


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 list of characters.

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


LÞṗ⁹ḲL¤K€ḟ”_⁼œ&ʋ@ƇṪ - Link: words, W; string, S
 Þ                  - sort (W) by:
L                   -   length (this is so we get final results which will match
                                in length when we use Ṫ at the end of the Link)
      ¤             - 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 four links as a dyad with swapped arguments:
          ”_        -     literal '_' character
         ḟ          -     filter discard (remove all '_'s from S)
             œ&     -     (S) multi-set intersection (current value)
            ⁼       -     equal? (S without '_'s == multi-set intersection?)
                  Ṫ - head (last result)
  • \$\begingroup\$ Pinging this because I'm curious if theres a way to shorten the naive fix. \$\endgroup\$
    – Razetime
    Oct 19, 2020 at 11:57
  • \$\begingroup\$ @Razetime Yes there was a way to do so, I've edited it in. \$\endgroup\$ Oct 19, 2020 at 12:36

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, 2018 at 22:42

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

C (gcc), 232 226 bytes

  • -23 bytes from @ceilingcat
  • +17 bytes for required header file

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.

*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?: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));}

Try it online!


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, 2018 at 23:02

05AB1E (legacy), 27 bytes


Can definitely be golfed a bit more, but this will do for now.

First input is the string, second a list of words. If multiple words are possible, it picks a random one.

Assumes the sentence always contains at least a single space. If this is not allowed, the # has to be replaced with ð¡.

Uses the legacy version because the zip-builtins work on strings, whereas these have to be character-lists in the new version of 05AB1E. In the new version, the ʒX‚ζεD'_åsË~}P} would have been 1 byte longer because of that: ʒSXS‚ζε'_åyË~}P}.

Try it online (with a small sample dictionary list).


#                   # Split the (implicit) first input-String on spaces
 ε                  # Map over each word:
  D                 #  Duplicate the current word
   '_åi            '#  If the word contains an underscore:
       U            #   Pop the copy and store it in variable `X`
        ʒ           #   Filter over the (implicit) second input-list of words:
         X‚         #    Pair `X` with the current word
           ζ        #    Zip/transpose, swapping rows/columns with spaces as default
                    #    filler if the strings are of unequal length
            ε       #    Map over each pair of characters
             D      #     Duplicate it
              '_å  '#     Check if the pair contains an underscore
             s      #     Swap to get the map-value again
              Ë     #     Check that both characters are the same
                 ~  #     Check that either of these were truthy
            }P      #    After the map: check if all pairs were truthy
        }Ω          #   After the filter: pop and push a random valid word
                    #  (implicit else: use the unmodified word from the duplicate)
 ]                  # Close both the if-statement and map
  ðý                # And join the list by spaces
                    # (after which the result is output implicitly)

Husk, 22 bytes


Try it online!

For each word in query text, goes through all words in the dictionary substituting matching characters for '_'. If, after doing this, the word is only '_'s, then it matched at all non-'_' characters, so it's a valid replacement.

 ḟoΛ='_żμ?'_³=⁰     # helper function: 
                    # finds word in arg2 that matches arg1 
                    # except at '_' characters.
ḟ                   # get first element that satisfies
 oΛ='_              # all elements are equal to '_'
                    # of
       żμ           # zip togethter arg2 and arg1 with
         ?   =⁰     # if they're equal
            ³       # then arg 2
          '_        # otherwise '_'
wm`₁⁰w²             # main program:
w                   # join with spaces
 m   w²             # map arg2 split on spaces 
  `₁⁰               # using helper function with arg1

Ruby, 53 bytes

->d,s{s.gsub(/\S+/){d.grep(/#{$&.tr ?_,?.}/)[0]||_1}}

Attempt This Online!


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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