笔试题 brotherword【tire || hash】

给定一个单词a，如果通过交换单词中字母的顺序可以得到另外的单词b，那么定义b是a的兄弟单词，例如单词army和mary互为兄弟单词。现在给定一个字典，用户输入一个单词，如何根据字典找出这个单词有哪些兄弟单词？要求时间和空间效率尽可能的高。

方案一：

用hash来做 head中保存的是排好序的字母顺序例如给你bac 那么head中保存的就是abc

然后建立hash表

 1 #include <iostream>
 2 #include <cstring>
 3 #include <cstdio>
 4 #include <map>
 5 using namespace std;
 6 
 7 const int maxn = 1005;
 8 
 9 map<string, int> head;
10 struct Edge {
11     string to;
12     int next;
13 }e[maxn];
14 int tot;
15 void init() {
16     head.clear();
17     tot = 1;
18 }
19 
20 void add(string s1, string s2) {
21     e[tot].to = s2;
22     e[tot].next = head[s1];
23     head[s1] = tot++;
24 }
25 
26 void cal(string s1) {
27     for(int i = head[s1]; i; i = e[i].next) {
28         cout << e[i].to << " ";
29     } puts("");
30 }
31 
32 int main() {
33     int n;
34     scanf("%d",&n);
35     for(int i = 0; i < n; i++) {
36         char s1[10], s2[10];
37         scanf("
%s",s1);
38         strcpy(s2, s1);
39         int l = strlen(s2);
40         sort(s2, s2 + l);
41         string x1 = s2;
42         string x2 = s1;
43         add(x1, x2);
44     }
45     for(int i = 0; i < n; i++) {
46         char s1[10], s2[10];
47         scanf("
%s",s1);
48         strcpy(s2, s1);
49         int l = strlen(s2);
50         sort(s2, s2 + l);
51         string x1 = s2;
52         string x2 = s1;
53         cal(x1);
54     }
55 }

View Code

方案二：

用字典树来做

用字典树建树的时候注意按照排好序的字符串建树，然后在叶子节点上放置改点的原串。