问题
给定一本英语单词词典，请找出所有的变位词集。所谓的变位词是指，组成各个单词的字母完全相同，只是字母排列的顺序不同。
例如，“pots”,”stop”和“tops”互为变位词，因为每个单词都可以通过改变其他单词中字母的顺序来得到。
解决思路
编程珠玑的变位词程序要按照三个步骤来执行，其中前一个步骤程序的输出作为下一个步骤程序的输入：
- 程序标识单词。
- 程序排序标识后的文件。
- 程序将这些单词压缩为每个变位词类一行的形式。
单词的字典的处理过程：
由以上可看出需要三个程序的处理。
sign程序
假设输入单词的长度不超过100，对每个输入的单词依照字母进行排序，将结果输入这个单词所对应的“签名”。
sort程序
程序排序后的输出的“签名”，对其输出的结果排序，如上图。
squash程序
将同一个变位词类中的各个单词放到同一行中。
程序代码
C++代码
完整例子：先按照字符排序，比较是否是同一个字符串，输出字符串1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
//最简洁的换位词
void main()
{
char s1[1000]="stop",s2[1000]="opst";
int len1,len2;
//字符的长度
len1=strlen(s1);
len2=strlen(s2);
cout<<"排序前"<<endl;
cout<<"s1---------------------------"<<endl;
for(int i=0;i<len1;i++){
cout<<s1[i];
}
cout<<"-----------------------------"<<endl;
cout<<"s2---------------------------"<<endl;
for(int i=0;i<len2;i++){
cout<<s2[i];
}
cout<<"-----------------------------"<<endl;
//对给定区间所有元素进行排序
//有一个数组int a[100]，要对从a[0]到a[99]的元素进行排序，只要写sort(a,a+100)就行了，默认的排序方式是升序
//按ASCII值大小排序
sort(s1,s1+len1);
sort(s2,s2+len2);
cout<<"排序后"<<endl;
cout<<"s1---------------------------"<<endl;
for(int i=0;i<len1;i++){
cout<<s1[i];
}
cout<<"-----------------------------"<<endl;
cout<<"s2---------------------------"<<endl;
for(int i=0;i<len2;i++){
cout<<s2[i];
}
cout<<"-----------------------------"<<endl;
//两个字符串自左向右逐个字符相比（按ASCII值大小相比较）
if(strcmp(s1,s2)==0){
cout<<"Yes"<<endl;
}else{
cout<<"No"<<endl;
}
}
字符排序：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define WORDMAX 100
//由小到大排序
int charcomp(const void *x , const void *y)
{
return *(char *)x - *(char *)y;
}
int main()
{
char word[WORDMAX], sig[WORDMAX];
while (scanf("%s", word) != EOF)
{
strcpy(sig, word);
//1 待排序数组首地址
//2 数组中待排序元素数量
//3 各元素的占用空间大小
//4 指向函数的指针，用于确定排序的顺序（排序规则）
//qsort(sig, strlen(sig), sizeof(char), charcomp);
//另一种排序
sort(sig,sig+strlen(sig));
printf("%s %s\n", sig, word);
}
return 0;
}
Java代码
1 | package 换位词; |
