SpellCheckAssist | Topcoder Archive

Problem Statement

When typing text, people often make small mistakes. Most modern editors provide tools to quickly fix such mistakes with the help of spell checkers. When the user misspells a word, the editor suggests a number of correct words that are similar to what the user typed.

Let us call words A and B similar if A can be transformed to B by exactly one of the following operations:

Insert one letter at any position.
Remove one letter at any position.
Change one letter at any position to any other letter.
Swap two adjacent letters.

You are given a String word and a String[] dictionary. word will not be equal to any element of dictionary. Return a int[] containing the 0-based indices of all the words in dictionary that are similar to word. The returned int[] must be sorted in ascending order.

Definition

Class:: SpellCheckAssist
Method:: suggestFixes
Parameters:: String, String[]
Returns:: int[]
Method signature:: int[] suggestFixes(String word, String[] dictionary)
(be sure your method is public)

Constraints

word will contain between 1 and 50 characters, inclusive.
word will contain only lowercase letters ('a'-'z').
dictionary will contain between 1 and 50 elements, inclusive.
Each elemenent of dictionary will contain between 1 and 50 characters, inclusive.
Each element of dictionary will contain only lowercase letters ('a'-'z').
All elements of dictionary will be distinct.
word will not be equal to any element of dictionary.

Examples

```
"helo"
```
```
{"help", "hell", "hello", "hole", "halt", "he"}
```
```
Returns: {0, 1, 2 }
```
"helo" can be transformed to "help" by changing "o" to "p". "helo" can be transformed to "hell" by changing "o" to "l". "helo" can be transformed to "hello" by inserting "l" after "e". However, "helo" cannot be transformed to "hole" because only adjacent letters can be swapped. Also "helo" cannot be transformed to "halt" because only one letter can be replaced. "helo" cannot be transformed to "he" because only one letter can be removed.

"abc"

{"zbc", "azc", "abz", "bc", "ac", "ab", "zabc", "azbc", "abzc", "abcz", "bac", "acb"}

Returns: {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 }

This example demonstrates all possible operations.

```
"x"
```
```
{"abc"}
```
```
Returns: { }
```

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.