import java.util.ArrayList;
import java.util.List;

class SpellUtils {

	// We don't want to add duplicate words
	private static void add(String str, List<String> words) {
		words.add(str);
	}
	private static void add(char[] str, List<String> words) {
		add(new String(str), words);
	}

	// Add words where two characters have been switched
	// Add n words, where each word has two characters switched
	private static void addSwitchedLetterWords(String str, List<String> words) {
		char[] arr = str.toCharArray();
		char[] tmp;

		for (int i = 0; i < arr.length - 1; ++i) {
			tmp = arr.clone();
			char t = tmp[i];
			tmp[i] = tmp[i+1];
			tmp[i+1] = t;
			add(tmp, words);
		}
	}

	// Add words where one letter has been replaced with another
	// Add n * 20 words, one for each letter
	// (except for the one that's already there) for each position in the string
	private static void addReplacedLetterWords(String str, List<String> words) {
		char[] arr = str.toCharArray();
		char[] tmp;

		for (int i = 0; i < str.length(); ++i) {
			for (char c = 'a'; c <= 'z'; ++c) {
				if (c == arr[i])
					continue;

				tmp = arr.clone();
				tmp[i] = c;
				add(tmp, words);
			}
		}
	}

	// Add words where one letter has been removed
	// Add n * 21 words, one for each letter for each position in the string
	private static void addRemovedLetterWords(String str, List<String> words) {
		for (int i = 0; i < str.length() + 1; ++i) {
			char[] arr = new char[str.length() + 1];

			int k = 0;
			for (int j = 0; j < arr.length; ++j) {
				if (j != i)
					arr[j] = str.charAt(k++);
			}

			char[] tmp;
			for (char c = 'a'; c <= 'z'; ++c) {
				tmp = arr.clone();
				tmp[i] = c;
				add(tmp, words);
			}
		}
	}

	// Add words where one letter has been added
	// Add n words, one removing a character for each position in the string
	private static void addAddedLetterWords(String str, List<String> words) {
		for (int i = 0; i < str.length(); ++i) {
			char[] arr = new char[str.length() - 1];

			int k = 0;
			for (int j = 0; j < arr.length + 1; ++j) {
				if (j != i) {
					arr[k++] = str.charAt(j);
				}
			}

			add(arr, words);
		}
	}

	public static List<String> similarWords(String str) {
		List<String> words = new ArrayList<>();

		addSwitchedLetterWords(str, words);
		addReplacedLetterWords(str, words);
		addRemovedLetterWords(str, words);
		addAddedLetterWords(str, words);

		return words;
	}
}