首页 > 代码库 > USTC OJ — 1008 Word Amalgamation（组合数学，全排列）
USTC OJ — 1008 Word Amalgamation（组合数学，全排列）
1. 题目描述
题目的输入数据有两部分，前一部分是dictionary，后一部分是待查的单词集合。
对于每一个待查单词word1，我们需要从dictionary中查找对应的词汇word2。查找规则是：word1和word2组成的字母集合（这里是多重集合）相等。
2. 算法设计
对于每一个待查单词word1，用它对应的字母集合构造全排列。
对于全排列中的每一个排列，去查找是否存在于dictionary中。如果存在，就保存下来。如果不存在，直接输出“NOT A VALID WORD”。
如果在dictionary中，匹配了多个单词，把它们按字典序排序，全部输出即可。
3. AC Code
1 #include <stdio.h> 2 #include <string.h> 3 #include <stdlib.h> 4 5 #define N 105 6 #define WORD_MAX_SIZE 10 7 8 char dictionary[N][WORD_MAX_SIZE]; // 字典 9 int dic_size; // 字典大小（字典中的word个数） 10 11 char scrambled_word[WORD_MAX_SIZE]; // 待查找word 12 13 char words[N][WORD_MAX_SIZE]; // 存放在字典中匹配查找到的单词 14 int words_num; // 纪录匹配的单词个数 15 16 void permutation_check(char* p_str, char* p_begin); 17 void swap(char* a, char* b); 18 void search_in_dictionary(char str[]); 19 void print(); 20 void del_newline_symbol(char* str); 21 int cmp(const void* a, const void* b); 22 23 int main() 24 { 25 int i = 0; 26 27 // freopen("in.txt", "r", stdin); 28 29 // load dictionary into memory 30 while ( NULL != fgets(dictionary[i], WORD_MAX_SIZE, stdin) ) 31 { 32 // 去掉读入的多余换行符 33 del_newline_symbol(dictionary[i]); 34 35 // load over 36 if ( 0 == strcmp(dictionary[i], "XXXXXX") ) 37 { 38 dic_size = i; 39 break; 40 } 41 ++i; 42 } 43 44 while ( NULL != fgets(scrambled_word, WORD_MAX_SIZE, stdin) ) 45 { 46 // 去掉读入的多余换行符 47 del_newline_symbol(scrambled_word); 48 49 // 检查结束 50 if ( 0 == strcmp(scrambled_word, "XXXXXX") ) 51 break; 52 53 // 初始化查找结果集合 54 memset(words, 0, sizeof(words[0][0]) * N * WORD_MAX_SIZE); 55 words_num = 0; 56 57 // 对scrambled_word生成全排列，依次检查每一个排列 58 permutation_check(scrambled_word, scrambled_word); 59 60 // output 当前的scrambled_word的查找结果 61 if ( 0 == words_num ) 62 printf("NOT A VALID WORD\n"); 63 else 64 print(); 65 printf("******\n"); 66 } 67 return 0; 68 } 69 70 void del_newline_symbol(char* str) 71 { 72 int len = strlen(str); 73 if ( ‘\n‘ == str[len-1] ) 74 str[len-1] = ‘\0‘; 75 } 76 77 void print() 78 { 79 int i = 0; 80 // 输出要求按照字典序递增，故先对words排序 81 qsort(words, words_num, sizeof(words[0]), cmp); 82 83 printf("%s\n", words[i]); 84 for ( i = 1; i < words_num; ++i ) 85 { 86 // 如果存在重复匹配，只输出一次 87 if ( 0 != strcmp(words[i], words[i-1]) ) 88 printf("%s\n", words[i]); 89 } 90 } 91 92 int cmp(const void* a, const void* b) 93 { 94 return strcmp((char *)a, (char *)b); 95 } 96 97 /* 98 * core algorithm: Permutation全排列算法 99 * */100 void permutation_check(char* p_str, char* p_begin)101 {102 char * p_ch;103 if ( ‘\0‘ == *p_begin )104 {105 search_in_dictionary(p_str);106 }107 else108 {109 for ( p_ch = p_begin; *p_ch != ‘\0‘; p_ch++ )110 {111 swap(p_begin, p_ch);112 permutation_check(p_str, p_begin+1);113 swap(p_begin, p_ch);114 }115 }116 }117 118 void swap(char* a, char* b)119 {120 char t = *a;121 *a = *b;122 *b = t;123 }124 125 void search_in_dictionary(char str[])126 {127 int i;128 for ( i = 0; i < dic_size; ++i )129 {130 // 从字典中找到了，纪录下来131 if ( 0 == strcmp(str, dictionary[i]) )132 {133 strncpy(words[words_num], str, WORD_MAX_SIZE);134 ++words_num;135 }136 }137 }
USTC OJ — 1008 Word Amalgamation（组合数学，全排列）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。