17998번 - Levenshtein Distance 다국어

The Levenshtein Distance between two strings is the smallest number of simple one-letter operations needed to change one string to the other. The operations are:

• Adding a letter anywhere in the string.
• Removing a letter from anywhere in the string.
• Changing any letter in the string to any other letter.

Given a specific alphabet and a particular query string, find all other unique strings from that alphabet that are at a Levenshtein Distance of 1 from the given string, and list them in alphabetical order, with no duplicates.

Note that the query string must not be in the list. Its Levenshtein Distance from itself is 0, not 1.

Input consists of exactly two lines. The first line of input contains a sequence of unique lower-case letters, in alphabetical order, with no spaces between them. This is the alphabet to use.

The second line contains a string s (2 ≤ |s| ≤ 100), which consists only of lower-case letters from the given alphabet. This is the query string.

Output a list, in alphabetical order, of all strings which are a Levenshtein Distance of 1 from the query string 𝒔. Output one word per line, with no duplicates.