# Guess a word if number of character matches are given

Page 1 of 1

## 4 Replies - 817 Views - Last Post: 08 July 2021 - 12:56 PMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'https://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=421316&amp;s=00eea1b815dc9c17d02ea00a755f98e2&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #1 java_exp

Reputation: 0
• Posts: 2
• Joined: 20-June 21

# Guess a word if number of character matches are given

Posted 20 June 2021 - 10:51 PM

You need to guess a word. You are provided with a list of Words with the number of character matches at the right position.

Example

input {{"MOXTE",3} , {"AXCDG",0},{"MOQRT",2},{"FOUSE",4},{"POWER",1}}

return "MOUSE"
Explanation:

```MOXTE    MO##E    3 matches
AXCDG    #####    0 matches
MOQRT    MO###    2 matches
FOUSE    #OUSE    4 matches
POWER    #O###    1 match

Result:  MOUSE

```

I tried using brute force. Max heap is not working. Any leads?

Is This A Good Question/Topic? 0

## Replies To: Guess a word if number of character matches are given

### #2 modi123_1

• Suitor #2

Reputation: 16302
• Posts: 64,852
• Joined: 12-June 08

## Re: Guess a word if number of character matches are given

Posted 20 June 2021 - 11:14 PM

What do you mean you 'tried using brute force'? In what way?

### #3 java_exp

Reputation: 0
• Posts: 2
• Joined: 20-June 21

## Re: Guess a word if number of character matches are given

Posted 20 June 2021 - 11:21 PM

Comparing each and every word and letter and finding the best fit.

### #4 NormR

• D.I.C Lover

Reputation: 870
• Posts: 6,679
• Joined: 25-December 13

## Re: Guess a word if number of character matches are given

Posted 21 June 2021 - 04:31 AM

Can you post the steps in your algorithm?

### #5 Piet Souris

Reputation: 44
• Posts: 201
• Joined: 01-December 15

## Re: Guess a word if number of character matches are given

Posted 08 July 2021 - 12:56 PM

There are 26 ^ 5 possible strings, which is quite large, although doable brute force.

A way to reduce that number considerably is to check all the given words that have one or more correct letters. For instance: the word "FOUSE" has 4 characters correct. Now, that means that the soliution can have an F in position 0, an O at position 1, et cetera. You could thus make a Map<position, Set<possible characters>>.
Then, correct this map for the words that have no correct letters. For instance, "AXCDG": we know that the solution does not have an A at position 0, et cetera.

We end up with this map:

0, [F, M, P]
1, [O]
2, [Q, U, W, X]
3, [E, R, S, T]
4, [E, R, T]

If we then take the cartesian product of the values, we end up with 144 possible solutions, and only MOUSE fits the bill.