我的解答,但是复杂度不是很满意,是一个指数级的复杂度.但是测试数据比较弱,还是ac了。在网上找了找，都是brute force的解法，不知道有没有更好的解法。
解答中犯了两个错误，第一个，map<int, vector<int>> 的定义不被接受。但是这肯定是一个合法的c++定义。第二个，忘了考虑映射字符间反向的约束。也就是"ab"可能会被翻译成"cc"，，这是错误的。字符间从源到目标，从目标到源，都应该不存在一对多的映射。
#include <iostream>#include <sstream>#include <fstream>#include <string>#include <vector>#include <queue>#include <map>#include <set>#include <stack>#include <assert.h>#include <algorithm>#include <math.h>#include <ctime>#include <functional>#include <string.h>#include <stdio.h>#include <numeric>#include <float.h>using namespace std;vector<string> words;vector<string> m_dic[81];vector<int> finalMatchRelation; bool findMatchString(int index, vector<int> matchedCharacter, vector<int> getMatched) {if (index >= words.size()) {finalMatchRelation = matchedCharacter;return true;}vector<int> matchedCharacterBackup = matchedCharacter;vector<int> getMatchedBackup = getMatched; int l = words[index].size();for (int i = 0; i < m_dic[l].size(); i++) {bool ok = true;for (int j = 0; j < words[index].size() && ok; j++) {int srcCharIndex = words[index][j] – 'a';int objCharIndex = m_dic[l][i][j] – 'a';if (matchedCharacter[srcCharIndex] == -1 && getMatched[objCharIndex] == -1) {matchedCharacter[srcCharIndex] = objCharIndex;getMatched[objCharIndex] = srcCharIndex;}else if (matchedCharacter[srcCharIndex] == (m_dic[l][i][j] – 'a')) {continue;}else {ok = false;}}if (ok) {bool goodResult = findMatchString(index + 1, matchedCharacter, getMatched);if (goodResult) {return true;}}matchedCharacter = matchedCharacterBackup;getMatched = getMatchedBackup; }return false;}int main() {string placeHolder;int n;cin >> n; getline(cin, placeHolder);for (int i = 0; i < n; i++) { string ts; getline(cin, ts); m_dic[ts.size()].push_back(ts); }string s; while (getline(cin, s)) {vector<int> matchRelation(26, -1), getMatched(26, -1);stringstream ss(s);string ts; words.clear();while (ss >> ts) {words.push_back(ts); }string result = "";if (findMatchString(0, matchRelation, getMatched)) {for (int i = 0; i < s.size(); i++) {if (s[i] == ' ')result.push_back(' ');elseresult.push_back('a' + finalMatchRelation[s[i] – 'a']);}}else {for (int i = 0; i < s.size(); i++) {if (s[i] == ' ')result.push_back(' ');elseresult.push_back('*');}}cout << result << endl; }return 0; }
远离城市的喧嚣，寻找一份宁静，
