Crypt Kicker 算法和解决方案，出了什么问题？
Crypt Kicker Algorithm and Solution, what went wrong?
问题描述：
Crypt kicker 算法 是一种众所周知的加密算法，但安全性较低。这个UVa问题就是根据这个方法来解密线。问题陈述如下：
843 Crypt Kicker
A common but insecure method of encrypting text is to permute the letters of the alphabet. That is, in the text, each letter of the alphabet is consistently replaced by some other letter. So as to ensure that the encryption is reversible, no two letters are replaced by the same letter. Your task is to decrypt several encoded lines of text, assuming that each line uses a different set of
replacements, and that all words in the decrypted text are from a dictionary of known words.
Input
The input consists of a line containing an integer n, followed by n lower case words, one per line, in alphabetical order. These n words comprise the dictionary of words which may appear in the decrypted text. Following the dictionary are several lines of input. Each line is encrypted as described above.
There are no more than 1000 words in the dictionary. No word exceeds 16 letters. The encrypted lines contain only lower case letters and spaces and do not exceed 80 characters in length.
Output
Decrypt each line and print it to standard output. If there is more than one solution, any will do. If
there is no solution, replace every letter of the alphabet by an asterisk.
Sample Input
6
and
dick
jane
puff
spot
yertle
bjvg xsb hxsn xsb qymm xsb rqat xsb pnetfn
xxxx yyy zzzz www yyyy aaa bbbb ccc dddddd
Sample Output
dick and jane and puff and spot and yertle
**** * **** * **** * **** * ******
出了什么问题？
我创建了一个 Java 代码来解决它。我使用的算法如下图所示。代码似乎是正确的。它通过了我提供给它的所有测试用例，包括 uDebug 个测试用例。然而，当我将我的代码提交给 UVA 在线法官时，它总是 returns 我错误的答案判决 ！ 谁能找出我的问题？代码是否有隐藏的缺陷？还是在线判断的问题？！
非常感谢任何帮助！
算法说明：
解决这个问题的第一个想法是排列字母表中的所有字母以找到映射。然而，这个解决方案的计算量很大。一个更好的想法是使用 backtracking。您将加密词映射到与加密词具有相同长度和模式的字典词。 [显示单词模式的含义：'abc' 可能映射到 'her' 但是，它不能映射到 'see'，因为模式不同“三个不同的字母单词不能映射到两个不同的字母词”我从 this discussion 中得到了这个美丽的想法。如果找到到第一个单词的映射，则移动到下一个单词并映射它。如果第二个单词没有解决方案，则返回第一个单词并尝试另一个映射，依此类推。如果没有合适的映射到第一个词，则声明无解。对于映射，我首先映射最长的单词，因为它们更难映射。
代码：
这是我的代码。我试图注释掉重要的行。但是，如果您发现任何混淆，请直接提问，我会详细解释。谢谢，
import java.util.*;
public class P843 {
public static void main(String[] args) {
Scanner c = new Scanner(System.in);
int dictionarySize = c.nextInt();
c.nextLine();
// get the dictionary from the input stream:
String[] words = new String[dictionarySize];
for (int i = 0; i < words.length; i++)
words[i] = c.nextLine();
// get encrypted input
String line = c.nextLine();
while (c.hasNextLine()) {
if (line.length() == 0) {
System.out.println();
line = c.nextLine();
continue;
}
ArrayList<String> eWordsList = new ArrayList<>();
for(String eWord : line.split(" "))
if(eWord.length() != 0)
eWordsList.add(eWord);
String[] eWords = eWordsList.toArray(new String[0]);
String[] dWords = decryptWords(eWords, words);
for (int i = 0; i < dWords.length; i++)
if (i != dWords.length - 1)
System.out.print(dWords[i] + " ");
else
System.out.println(dWords[i]);
line = c.nextLine();
}
}
private static String[] decryptWords(String[] eWords, String[] words) {
String[] dWords = new String[eWords.length];
// get copy of the dWords so that the original version not destroyed
String[] eWordsCopy = Arrays.copyOf(eWords, eWords.length);
// sort by length from the greatest to the smallest
Arrays.sort(eWordsCopy, new Comparator<String>() {
@Override
public int compare(String w1, String w2) {
return Integer.compare(w2.length(), w1.length());
}
});
// initialize a key array to hold decrypted letters:
char[][] keyArray = new char[2][26];
for (int i = 0; i < 26; i++) {
keyArray[0][i] = (char) ('a' + i);
keyArray[1][i] = '*';
}
// restore keyArray original values if there is no solution to all words
if (!matchWords(words, eWordsCopy, keyArray))
for (int i = 0; i < 26; i++) {
keyArray[0][i] = (char) ('a' + i);
keyArray[1][i] = '*';
}
for (int i = 0; i < eWords.length; i++) {
StringBuilder temp = new StringBuilder();
for (int j = 0; j < eWords[i].length(); j++)
temp.append(keyArray[1][eWords[i].charAt(j) - 97]);
dWords[i] = temp.toString();
}
return dWords;
}
private static boolean matchWords(String[] words, String[] eWords, char[][] keyArray) {
ArrayList<String> promisingWords = new ArrayList<>();
String eWord = eWords[0];
// store the current state of keyArray
char[][] originalKeyArray = new char[2][26];
for (int i = 0; i < keyArray.length; i++)
if (keyArray[i].length >= 0) System.arraycopy(keyArray[i], 0, originalKeyArray[i], 0, keyArray[i].length);
// get promising words that may match
for (String word : words)
if (word.length() == eWord.length()
&& wordPattern(word).equals(wordPattern(eWord)))
promisingWords.add(word);
for (String word : promisingWords) {
if (mapWord(eWord, word, keyArray)) {
if (eWords.length > 1) {
// recursive call:
if (matchWords(words, Arrays.copyOfRange(eWords, 1, eWords.length), keyArray))
return true;
else {
// remove the word from the dictionary to try another one
for (int i = 0; i < keyArray.length; i++)
if (keyArray[i].length >= 0)
System.arraycopy(originalKeyArray[i], 0, keyArray[i], 0, keyArray[i].length);
}
}
// if there are now decrypted words, then return true
else
return true;
}
}
// if there is no word mapped, then return false
return false;
}
private static boolean mapWord(String eWord, String word, char[][] keyArray) {
// store the current state of keyArray
char[][] originalKeyArray = new char[2][26];
for (int i = 0; i < keyArray.length; i++)
if (keyArray[i].length >= 0) System.arraycopy(keyArray[i], 0, originalKeyArray[i], 0, keyArray[i].length);
// check one-to-one from the decrypted word to the dictionary word:
for (int i = 0; i < eWord.length(); i++)
if ((keyArray[1][eWord.charAt(i) - 97] != word.charAt(i)
&& keyArray[1][eWord.charAt(i) - 97] != '*')
|| !isLetterMapped(eWord.charAt(i), word.charAt(i), keyArray)) {
// restore original array back
for (int j = 0; j < keyArray.length; j++)
if (keyArray[j].length >= 0)
System.arraycopy(originalKeyArray[j], 0, keyArray[j], 0, keyArray[j].length);
return false;
}
// update the key array:
else
keyArray[1][eWord.charAt(i) - 97] = word.charAt(i);
return true;
}
private static boolean isLetterMapped(char eLetter, char letter, char[][] keyArray) {
for (int i = 0; i < 26; i++)
if (keyArray[1][i] == letter && keyArray[0][i] != eLetter)
return false;
return true;
}
// generate a word pattern
private static String wordPattern(String word) {
if (word.length() > 0) {
StringBuilder mapped = new StringBuilder();
int count = 0;
HashMap<Character, Character> mapping = new HashMap<>();
for (int i = 0; i < word.length(); i++)
if (!mapping.containsKey(word.charAt(i)))
mapping.put(word.charAt(i), (char) (48 + count++));
for (int i = 0; i < word.length(); i++)
mapped.append(mapping.get(word.charAt(i)));
return mapped.toString();
} else {
return "";
}
}
}
主要问题似乎是您的程序无法解密（或处理）最后一行输入。发生这种情况是因为循环条件 c.hasNextLine() 被评估 在 你已经阅读了你将要在循环迭代中处理的行。
此外，我观察到您解决的问题与挑战提出的问题不同，尽管是密切相关的问题。你应该
Decrypt each line
（强调已添加），但您实际做的是解密每行的单词。输入描述不承诺加密行将没有前导或尾随白色space，或者相邻单词之间不会超过一个space。如果其中任何一个发生，那么您的程序不会在其输出中重现它们。
此外，虽然我倾向于将问题描述理解为字典中的单词是单独一行的，没有任何前导或尾随白色space，但如果事实并非如此，那么你的阅读它们的方法包括 spaces。只需 trim() 在每个输入上输入即可轻松防止这种情况。
我最大的文体批评是：不要省略循环主体或 if 或 else 块周围的大括号 ，即使这些主体包含只有一个声明。这样做会使您的代码更难阅读，并为未来的维护者（包括未来的您）埋下陷阱。在过去几年中，此类遗漏至少导致了一个备受瞩目的安全问题。
在@John Bollinger 的帮助下，问题终于得到解决并被接受。有关我的愚蠢错误的更多详细信息，请参阅上面的 :( 在代码中。
我现在在这里发布代码的最终版本。所做的改进包括：
- 正在修复从输入流读取时的错误。
- 将 keyArray 从二维数组更改为一维数组。
- 通过添加大括号和注释更多行来进一步美化代码。
代码在这里：
import java.util.*;
public class P843 {
public static void main(String[] args) {
Scanner c = new Scanner(System.in);
int dictionarySize = c.nextInt();
// this line is to flush out the input stream
c.nextLine();
// get the dictionary from the input stream:
String[] words = new String[dictionarySize];
for (int i = 0; i < words.length; i++) {
words[i] = c.nextLine();
// remove white spaces surrounding dictionary words if there is any
words[i] = words[i].trim();
}
// get encrypted input
String line;
while (c.hasNextLine()) {
line = c.nextLine();
if (line.length() == 0) {
System.out.println();
continue;
}
// remove whitespaces
String[] eWords = line.split(" ");
for (int i = 0; i < eWords.length; i++) {
eWords[i] = eWords[i].trim();
}
// decrypt words:
String[] dWords = decryptWords(eWords, words);
// print the decrypted line
for (int i = 0; i < dWords.length; i++) {
if (i != dWords.length - 1) {
System.out.print(dWords[i] + " ");
} else {
System.out.println(dWords[i]);
}
}
}
}
private static String[] decryptWords(String[] eWords, String[] words) {
String[] dWords = new String[eWords.length];
// get copy of the dWords so that the original version not destroyed
String[] eWordsCopy = Arrays.copyOf(eWords, eWords.length);
// sort by length from the greatest to the smallest
Arrays.sort(eWordsCopy, new Comparator<String>() {
@Override
public int compare(String w1, String w2) {
return Integer.compare(w2.length(), w1.length());
}
});
// initialize a key array to hold decrypted letters:
// for example: 'a' would be mapped to keyArray[0] and 'z' would be mapped to keyArray[25]
char[] keyArray = new char[26];
for (int i = 0; i < 26; i++) {
// initialize the keyArray to '*'
keyArray[i] = '*';
}
// restore keyArray original values if there is no solution to all words
if (!matchWords(words, eWordsCopy, keyArray)) {
for (int i = 0; i < 26; i++) {
keyArray[i] = '*';
}
}
// decrypt line using the mapping stored in keyArray
for (int i = 0; i < eWords.length; i++) {
StringBuilder temp = new StringBuilder();
for (int j = 0; j < eWords[i].length(); j++) {
temp.append(keyArray[eWords[i].charAt(j) - 97]);
}
dWords[i] = temp.toString();
}
return dWords;
}
private static boolean matchWords(String[] words, String[] eWords, char[] keyArray) {
ArrayList<String> promisingWords = new ArrayList<>();
String eWord = eWords[0];
// store the current state of keyArray
char[] originalKeyArray = new char[26];
System.arraycopy(keyArray, 0, originalKeyArray, 0, originalKeyArray.length);
// get promising words that may match
for (String word : words) {
if (word.length() == eWord.length()
&& wordPattern(word).equals(wordPattern(eWord))) {
promisingWords.add(word);
}
}
for (String word : promisingWords) {
if (mapWord(eWord, word, keyArray)) {
if (eWords.length > 1) {
// recursive call:
if (matchWords(words, Arrays.copyOfRange(eWords, 1, eWords.length), keyArray))
return true;
else {
// remove the word from the dictionary [by restoring the keyArray original values]
// and try another one
System.arraycopy(originalKeyArray, 0, keyArray, 0, keyArray.length);
}
} else // if there is no more decrypted words, then return true
return true;
}
}
// if there is no suitable mapping, return false
return false;
}
private static boolean mapWord(String eWord, String word, char[] keyArray) {
// store the current state of keyArray
char[] originalKeyArray = new char[26];
System.arraycopy(keyArray, 0, originalKeyArray, 0, keyArray.length);
// check one-to-one from the decrypted word to the dictionary word:
for (int i = 0; i < eWord.length(); i++) {
if ((keyArray[eWord.charAt(i) - 97] != word.charAt(i)
&& keyArray[eWord.charAt(i) - 97] != '*')
|| !isLetterMapped(eWord.charAt(i), word.charAt(i), keyArray)) {
// restore original array back
System.arraycopy(originalKeyArray, 0, keyArray, 0, keyArray.length);
return false;
}
// update the key array:
else {
keyArray[eWord.charAt(i) - 97] = word.charAt(i);
}
}
return true;
}
private static boolean isLetterMapped(char eLetter, char letter, char[] keyArray) {
for (int i = 0; i < 26; i++) {
if (keyArray[i] == letter && i != (eLetter - 97)) {
return false;
}
}
return true;
}
// generate a word pattern
private static String wordPattern(String word) {
if (word.length() > 0) {
StringBuilder mapped = new StringBuilder();
int count = 0;
HashMap<Character, Character> mapping = new HashMap<>();
for (int i = 0; i < word.length(); i++) {
if (!mapping.containsKey(word.charAt(i))) {
mapping.put(word.charAt(i), (char) (48 + count++));
}
}
for (int i = 0; i < word.length(); i++) {
mapped.append(mapping.get(word.charAt(i)));
}
return mapped.toString();
} else {
return "";
}
}
}
如果您使用 Java 作为武器来解决本书编程挑战书中的类似问题，非常欢迎您路过并浏览 my repository 我打算放的地方更多解决方案和提示。
谢谢
问题描述：
Crypt kicker 算法 是一种众所周知的加密算法，但安全性较低。这个UVa问题就是根据这个方法来解密线。问题陈述如下：
843 Crypt Kicker
A common but insecure method of encrypting text is to permute the letters of the alphabet. That is, in the text, each letter of the alphabet is consistently replaced by some other letter. So as to ensure that the encryption is reversible, no two letters are replaced by the same letter. Your task is to decrypt several encoded lines of text, assuming that each line uses a different set of replacements, and that all words in the decrypted text are from a dictionary of known words.
Input
The input consists of a line containing an integer n, followed by n lower case words, one per line, in alphabetical order. These n words comprise the dictionary of words which may appear in the decrypted text. Following the dictionary are several lines of input. Each line is encrypted as described above. There are no more than 1000 words in the dictionary. No word exceeds 16 letters. The encrypted lines contain only lower case letters and spaces and do not exceed 80 characters in length.
Output
Decrypt each line and print it to standard output. If there is more than one solution, any will do. If there is no solution, replace every letter of the alphabet by an asterisk.
Sample Input
6 and dick jane puff spot yertle bjvg xsb hxsn xsb qymm xsb rqat xsb pnetfn xxxx yyy zzzz www yyyy aaa bbbb ccc dddddd
Sample Output
dick and jane and puff and spot and yertle
**** * **** * **** * **** * ******
出了什么问题？
我创建了一个 Java 代码来解决它。我使用的算法如下图所示。代码似乎是正确的。它通过了我提供给它的所有测试用例，包括 uDebug 个测试用例。然而，当我将我的代码提交给 UVA 在线法官时，它总是 returns 我错误的答案判决 ！ 谁能找出我的问题？代码是否有隐藏的缺陷？还是在线判断的问题？！
非常感谢任何帮助！
算法说明：
解决这个问题的第一个想法是排列字母表中的所有字母以找到映射。然而，这个解决方案的计算量很大。一个更好的想法是使用 backtracking。您将加密词映射到与加密词具有相同长度和模式的字典词。 [显示单词模式的含义：'abc' 可能映射到 'her' 但是，它不能映射到 'see'，因为模式不同“三个不同的字母单词不能映射到两个不同的字母词”我从 this discussion 中得到了这个美丽的想法。如果找到到第一个单词的映射，则移动到下一个单词并映射它。如果第二个单词没有解决方案，则返回第一个单词并尝试另一个映射，依此类推。如果没有合适的映射到第一个词，则声明无解。对于映射，我首先映射最长的单词，因为它们更难映射。
代码：
这是我的代码。我试图注释掉重要的行。但是，如果您发现任何混淆，请直接提问，我会详细解释。谢谢，
import java.util.*;
public class P843 {
public static void main(String[] args) {
Scanner c = new Scanner(System.in);
int dictionarySize = c.nextInt();
c.nextLine();
// get the dictionary from the input stream:
String[] words = new String[dictionarySize];
for (int i = 0; i < words.length; i++)
words[i] = c.nextLine();
// get encrypted input
String line = c.nextLine();
while (c.hasNextLine()) {
if (line.length() == 0) {
System.out.println();
line = c.nextLine();
continue;
}
ArrayList<String> eWordsList = new ArrayList<>();
for(String eWord : line.split(" "))
if(eWord.length() != 0)
eWordsList.add(eWord);
String[] eWords = eWordsList.toArray(new String[0]);
String[] dWords = decryptWords(eWords, words);
for (int i = 0; i < dWords.length; i++)
if (i != dWords.length - 1)
System.out.print(dWords[i] + " ");
else
System.out.println(dWords[i]);
line = c.nextLine();
}
}
private static String[] decryptWords(String[] eWords, String[] words) {
String[] dWords = new String[eWords.length];
// get copy of the dWords so that the original version not destroyed
String[] eWordsCopy = Arrays.copyOf(eWords, eWords.length);
// sort by length from the greatest to the smallest
Arrays.sort(eWordsCopy, new Comparator<String>() {
@Override
public int compare(String w1, String w2) {
return Integer.compare(w2.length(), w1.length());
}
});
// initialize a key array to hold decrypted letters:
char[][] keyArray = new char[2][26];
for (int i = 0; i < 26; i++) {
keyArray[0][i] = (char) ('a' + i);
keyArray[1][i] = '*';
}
// restore keyArray original values if there is no solution to all words
if (!matchWords(words, eWordsCopy, keyArray))
for (int i = 0; i < 26; i++) {
keyArray[0][i] = (char) ('a' + i);
keyArray[1][i] = '*';
}
for (int i = 0; i < eWords.length; i++) {
StringBuilder temp = new StringBuilder();
for (int j = 0; j < eWords[i].length(); j++)
temp.append(keyArray[1][eWords[i].charAt(j) - 97]);
dWords[i] = temp.toString();
}
return dWords;
}
private static boolean matchWords(String[] words, String[] eWords, char[][] keyArray) {
ArrayList<String> promisingWords = new ArrayList<>();
String eWord = eWords[0];
// store the current state of keyArray
char[][] originalKeyArray = new char[2][26];
for (int i = 0; i < keyArray.length; i++)
if (keyArray[i].length >= 0) System.arraycopy(keyArray[i], 0, originalKeyArray[i], 0, keyArray[i].length);
// get promising words that may match
for (String word : words)
if (word.length() == eWord.length()
&& wordPattern(word).equals(wordPattern(eWord)))
promisingWords.add(word);
for (String word : promisingWords) {
if (mapWord(eWord, word, keyArray)) {
if (eWords.length > 1) {
// recursive call:
if (matchWords(words, Arrays.copyOfRange(eWords, 1, eWords.length), keyArray))
return true;
else {
// remove the word from the dictionary to try another one
for (int i = 0; i < keyArray.length; i++)
if (keyArray[i].length >= 0)
System.arraycopy(originalKeyArray[i], 0, keyArray[i], 0, keyArray[i].length);
}
}
// if there are now decrypted words, then return true
else
return true;
}
}
// if there is no word mapped, then return false
return false;
}
private static boolean mapWord(String eWord, String word, char[][] keyArray) {
// store the current state of keyArray
char[][] originalKeyArray = new char[2][26];
for (int i = 0; i < keyArray.length; i++)
if (keyArray[i].length >= 0) System.arraycopy(keyArray[i], 0, originalKeyArray[i], 0, keyArray[i].length);
// check one-to-one from the decrypted word to the dictionary word:
for (int i = 0; i < eWord.length(); i++)
if ((keyArray[1][eWord.charAt(i) - 97] != word.charAt(i)
&& keyArray[1][eWord.charAt(i) - 97] != '*')
|| !isLetterMapped(eWord.charAt(i), word.charAt(i), keyArray)) {
// restore original array back
for (int j = 0; j < keyArray.length; j++)
if (keyArray[j].length >= 0)
System.arraycopy(originalKeyArray[j], 0, keyArray[j], 0, keyArray[j].length);
return false;
}
// update the key array:
else
keyArray[1][eWord.charAt(i) - 97] = word.charAt(i);
return true;
}
private static boolean isLetterMapped(char eLetter, char letter, char[][] keyArray) {
for (int i = 0; i < 26; i++)
if (keyArray[1][i] == letter && keyArray[0][i] != eLetter)
return false;
return true;
}
// generate a word pattern
private static String wordPattern(String word) {
if (word.length() > 0) {
StringBuilder mapped = new StringBuilder();
int count = 0;
HashMap<Character, Character> mapping = new HashMap<>();
for (int i = 0; i < word.length(); i++)
if (!mapping.containsKey(word.charAt(i)))
mapping.put(word.charAt(i), (char) (48 + count++));
for (int i = 0; i < word.length(); i++)
mapped.append(mapping.get(word.charAt(i)));
return mapped.toString();
} else {
return "";
}
}
}
主要问题似乎是您的程序无法解密（或处理）最后一行输入。发生这种情况是因为循环条件 c.hasNextLine() 被评估 在 你已经阅读了你将要在循环迭代中处理的行。
此外，我观察到您解决的问题与挑战提出的问题不同，尽管是密切相关的问题。你应该
Decrypt each line
（强调已添加），但您实际做的是解密每行的单词。输入描述不承诺加密行将没有前导或尾随白色space，或者相邻单词之间不会超过一个space。如果其中任何一个发生，那么您的程序不会在其输出中重现它们。
此外，虽然我倾向于将问题描述理解为字典中的单词是单独一行的，没有任何前导或尾随白色space，但如果事实并非如此，那么你的阅读它们的方法包括 spaces。只需 trim() 在每个输入上输入即可轻松防止这种情况。
我最大的文体批评是：不要省略循环主体或 if 或 else 块周围的大括号 ，即使这些主体包含只有一个声明。这样做会使您的代码更难阅读，并为未来的维护者（包括未来的您）埋下陷阱。在过去几年中，此类遗漏至少导致了一个备受瞩目的安全问题。
在@John Bollinger 的帮助下，问题终于得到解决并被接受。有关我的愚蠢错误的更多详细信息，请参阅上面的
我现在在这里发布代码的最终版本。所做的改进包括：
- 正在修复从输入流读取时的错误。
- 将 keyArray 从二维数组更改为一维数组。
- 通过添加大括号和注释更多行来进一步美化代码。
代码在这里：
import java.util.*;
public class P843 {
public static void main(String[] args) {
Scanner c = new Scanner(System.in);
int dictionarySize = c.nextInt();
// this line is to flush out the input stream
c.nextLine();
// get the dictionary from the input stream:
String[] words = new String[dictionarySize];
for (int i = 0; i < words.length; i++) {
words[i] = c.nextLine();
// remove white spaces surrounding dictionary words if there is any
words[i] = words[i].trim();
}
// get encrypted input
String line;
while (c.hasNextLine()) {
line = c.nextLine();
if (line.length() == 0) {
System.out.println();
continue;
}
// remove whitespaces
String[] eWords = line.split(" ");
for (int i = 0; i < eWords.length; i++) {
eWords[i] = eWords[i].trim();
}
// decrypt words:
String[] dWords = decryptWords(eWords, words);
// print the decrypted line
for (int i = 0; i < dWords.length; i++) {
if (i != dWords.length - 1) {
System.out.print(dWords[i] + " ");
} else {
System.out.println(dWords[i]);
}
}
}
}
private static String[] decryptWords(String[] eWords, String[] words) {
String[] dWords = new String[eWords.length];
// get copy of the dWords so that the original version not destroyed
String[] eWordsCopy = Arrays.copyOf(eWords, eWords.length);
// sort by length from the greatest to the smallest
Arrays.sort(eWordsCopy, new Comparator<String>() {
@Override
public int compare(String w1, String w2) {
return Integer.compare(w2.length(), w1.length());
}
});
// initialize a key array to hold decrypted letters:
// for example: 'a' would be mapped to keyArray[0] and 'z' would be mapped to keyArray[25]
char[] keyArray = new char[26];
for (int i = 0; i < 26; i++) {
// initialize the keyArray to '*'
keyArray[i] = '*';
}
// restore keyArray original values if there is no solution to all words
if (!matchWords(words, eWordsCopy, keyArray)) {
for (int i = 0; i < 26; i++) {
keyArray[i] = '*';
}
}
// decrypt line using the mapping stored in keyArray
for (int i = 0; i < eWords.length; i++) {
StringBuilder temp = new StringBuilder();
for (int j = 0; j < eWords[i].length(); j++) {
temp.append(keyArray[eWords[i].charAt(j) - 97]);
}
dWords[i] = temp.toString();
}
return dWords;
}
private static boolean matchWords(String[] words, String[] eWords, char[] keyArray) {
ArrayList<String> promisingWords = new ArrayList<>();
String eWord = eWords[0];
// store the current state of keyArray
char[] originalKeyArray = new char[26];
System.arraycopy(keyArray, 0, originalKeyArray, 0, originalKeyArray.length);
// get promising words that may match
for (String word : words) {
if (word.length() == eWord.length()
&& wordPattern(word).equals(wordPattern(eWord))) {
promisingWords.add(word);
}
}
for (String word : promisingWords) {
if (mapWord(eWord, word, keyArray)) {
if (eWords.length > 1) {
// recursive call:
if (matchWords(words, Arrays.copyOfRange(eWords, 1, eWords.length), keyArray))
return true;
else {
// remove the word from the dictionary [by restoring the keyArray original values]
// and try another one
System.arraycopy(originalKeyArray, 0, keyArray, 0, keyArray.length);
}
} else // if there is no more decrypted words, then return true
return true;
}
}
// if there is no suitable mapping, return false
return false;
}
private static boolean mapWord(String eWord, String word, char[] keyArray) {
// store the current state of keyArray
char[] originalKeyArray = new char[26];
System.arraycopy(keyArray, 0, originalKeyArray, 0, keyArray.length);
// check one-to-one from the decrypted word to the dictionary word:
for (int i = 0; i < eWord.length(); i++) {
if ((keyArray[eWord.charAt(i) - 97] != word.charAt(i)
&& keyArray[eWord.charAt(i) - 97] != '*')
|| !isLetterMapped(eWord.charAt(i), word.charAt(i), keyArray)) {
// restore original array back
System.arraycopy(originalKeyArray, 0, keyArray, 0, keyArray.length);
return false;
}
// update the key array:
else {
keyArray[eWord.charAt(i) - 97] = word.charAt(i);
}
}
return true;
}
private static boolean isLetterMapped(char eLetter, char letter, char[] keyArray) {
for (int i = 0; i < 26; i++) {
if (keyArray[i] == letter && i != (eLetter - 97)) {
return false;
}
}
return true;
}
// generate a word pattern
private static String wordPattern(String word) {
if (word.length() > 0) {
StringBuilder mapped = new StringBuilder();
int count = 0;
HashMap<Character, Character> mapping = new HashMap<>();
for (int i = 0; i < word.length(); i++) {
if (!mapping.containsKey(word.charAt(i))) {
mapping.put(word.charAt(i), (char) (48 + count++));
}
}
for (int i = 0; i < word.length(); i++) {
mapped.append(mapping.get(word.charAt(i)));
}
return mapped.toString();
} else {
return "";
}
}
}
如果您使用 Java 作为武器来解决本书编程挑战书中的类似问题，非常欢迎您路过并浏览 my repository 我打算放的地方更多解决方案和提示。
谢谢