据我了解，您有一个字母表中的输入字符串 S（我们称之为 A1），并且您想将其转换为字符串 S'，它在另一个字母表 A2 中是等效的。实际上，如果我理解正确，您想要生成一个可能等同于 S 的输出字符串列表 [S'1,S'2,...,S'n]。
想到的一种方法是为 A2 中有效单词列表中的每个单词生成 A1 中匹配的字符串列表。使用您编辑中的示例，我们有
px->ac
qy->ac
pr->ab
（为了清楚起见，我添加了一个额外的有效词pr）
现在我们知道了哪些可能的输入符号系列将始终映射到一个有效的单词，我们可以使用我们的表来构建一个Trie。
每个节点将持有一个指向 A2 中有效单词列表的指针，该列表映射到 A1 中的符号序列，这些符号序列形成从 Trie 的根到当前节点的路径。
因此，对于我们的示例，Trie 看起来像这样
Root (empty)
| a
|
V
+---Node (empty)---+
| b | c
| |
V V
Node (px,qy) Node (pr)
从根节点开始，随着符号被消耗，从当前节点到其子节点的转换被标记为消耗的符号，直到我们读取整个字符串。如果在任何时候没有为该符号定义转换，则输入的字符串在我们的 trie 中不存在，因此不会映射到目标语言中的有效单词。否则，在该过程结束时，与当前节点关联的单词列表是输入字符串映射到的有效单词列表。
除了构建 trie 的初始成本（如果我们不希望更改有效单词列表，可以预先构建 trie），这需要 O(n) 的输入长度才能找到有效的映射列表字。
使用 Trie 还提供了一个优势，您还可以使用它来查找可以通过在输入末尾添加更多符号来生成的所有有效单词的列表 - 即前缀匹配。例如，如果输入符号“a”，我们可以使用 trie 查找所有可以以“a”开头的有效单词（“px”、“qr”、“py”）。但这样做并不像找到完全匹配那样快。
这是一个解决方案的快速破解（Java）：
import java.util.*;
class TrieNode{
// child nodes - size of array depends on your alphabet size,
// her we are only using the lowercase English characters 'a'-'z'
TrieNode[] next=new TrieNode[26];
List<String> words;
public TrieNode(){
words=new ArrayList<String>();
}
}
class Trie{
private TrieNode root=null;
public void addWord(String sourceLanguage, String targetLanguage){
root=add(root,sourceLanguage.toCharArray(),0,targetLanguage);
}
private static int convertToIndex(char c){ // you need to change this for your alphabet
return (c-'a');
}
private TrieNode add(TrieNode cur, char[] s, int pos, String targ){
if (cur==null){
cur=new TrieNode();
}
if (s.length==pos){
cur.words.add(targ);
}
else{
cur.next[convertToIndex(s[pos])]=add(cur.next[convertToIndex(s[pos])],s,pos+1,targ);
}
return cur;
}
public List<String> findMatches(String text){
return find(root,text.toCharArray(),0);
}
private List<String> find(TrieNode cur, char[] s, int pos){
if (cur==null) return new ArrayList<String>();
else if (pos==s.length){
return cur.words;
}
else{
return find(cur.next[convertToIndex(s[pos])],s,pos+1);
}
}
}
class MyMiniTransliiterator{
public static void main(String args[]){
Trie t=new Trie();
t.addWord("ac","px");
t.addWord("ac","qy");
t.addWord("ab","pr");
System.out.println(t.findMatches("ac")); // prints [px,qy]
System.out.println(t.findMatches("ab")); // prints [pr]
System.out.println(t.findMatches("ba")); // prints empty list since this does not match anything
}
}
这是一个非常简单的 trie，没有压缩或加速，仅适用于输入语言的小写英文字符。但它可以很容易地修改为其他字符集。