translation.cpp

#include <iostream>
#include <set>
#include <vector>

using namespace std;

set<char> defaultCharSet = {};

void addEdit(int lastEdit, set<string>* result, vector<string>* expand, string s) {
	if (result->count(s)) return;
	result->insert(s);
	if (!lastEdit) expand->push_back(s);
}

set<string> makeEdits(string S, int count = 1, set<char> charSet = defaultCharSet) {
//	cout << charSet.size() << endl;
	set<string> result;
	result.insert(S);
	vector<string> expand;
	expand.push_back(S);
//	cout << "expand 1 [" << expand[0] << "]" << endl;
	int lastEdit = 0;
	for (int edit = 0; edit < count; edit++) {
		vector<string> editing;
		for (string tocopy : expand) editing.push_back(tocopy);
//		cout << "editing: ";
//		for (string elem : editing) cout << elem << " ";
//		cout << endl;
		expand.clear();
		lastEdit = (edit == count + 1);
		for (string eString : editing) {
			string clone;
			for (int i = 0; i < eString.length(); i++) {
				string right = eString.substr(i + 1);
				clone = eString.substr(0, i); clone += right;
				addEdit(lastEdit, &result, &expand, clone);
				for (char newChar : charSet) {
					string charString(1, newChar);
					string ccCharString(1, eString.at(i));
					clone = eString.substr(0, i); clone += charString; clone += ccCharString; clone += right;
					addEdit(lastEdit, &result, &expand, clone);
					clone = eString.substr(0, i); clone += charString; clone += right;
					addEdit(lastEdit, &result, &expand, clone);
				}
			}
			for (char newChar : charSet) {
				string charString(1, newChar);
				clone = eString.substr(0, eString.length()); clone += charString;
				addEdit(lastEdit, &result, &expand, clone);
			}
		}
	}
	return result;
}

int main() {
	for (int i = 9; i < 14; i++) defaultCharSet.insert((char) i);
	for (int i = 32; i < 127; i++) defaultCharSet.insert((char) i);
	set<string> result = makeEdits("aaaaaaaaaa", 1);
	cout << result.size() << endl;
}