[编程题]查找兄弟单词

阳光穿透心脏的1/2处 2022-07-14 15:12 150阅读 0赞

> Talk is cheap, show me the code.

### 一、问题描述 ###

实现一个可存储若干个单词的字典。用户可以  
在字典中加入单词；  
查找指定单词在字典中的兄弟单词个数；  
查找指定单词的指定序号的兄弟单词，指定序号指字典中兄弟单词按字典顺序排序后的序号(从1开始)；  
  
清空字典中所有单词。

定义，格式说明  
**单词：**由小写英文字母组成，不含其它字符。  
**兄弟单词：**给定一个单词X，如果通过任意交换单词中字母的位置得到不同的单词Y，那么定义Y是X的兄弟单词。  
  
**字典顺序：**两个单词(字母按照自左向右顺序)，先以第一个字母作为排序的基准，如果第一个字母相同，就用第二个字母为基准，如果第二个字母相同就以第三个字母为基准。以此类推，如果到某个字母不相同，字母顺序在前的那个单词顺序在前。如果短单词是长单词从首字母开始连续的一部分，短单词顺序在前。

举例：bca是abc的兄弟单词；abc和abc是相同单词，不是兄弟单词。

规格：  
0 <= 字典中所含单词个数 <= 1000  
1 <= 单词所含字母数 <= 50  
测试用例保证：接口中输入不会超出如上约束。

**输入描述：**

> 先输入字典中单词的个数，再输入n个单词作为字典单词。  
> 输入一个单词，查找其在字典中兄弟单词的个数  
> 再输入数字n

**输出描述：**

> 根据输入，输出查找到的兄弟单词的个数

**输入例子：**

3
    abc
    bca
    cab
    abc
    1

**输出例子：**

2
    bca

### 二、问题分析 ###

问题的难点在于查找兄弟单词，如果考虑对于查询单词列举出它所有可能得兄弟单词，然后再去在输入字典中查询，那么列举所有可能兄弟单词将会是一个非常复杂的工作，复杂度是阶乘的，所以这种思路不可行，那么只能考虑对于输入的一个单词逐个地与输入字典中的单词进行比较，判断输入字典中的单词是否查询单词的兄弟单词，可以对单词进行排序，那么如果是兄弟单词，排序后的单词应该是相等的。

#include <iostream>
    #include <vector>
    #include <iterator>
    #include <string>
    #include <algorithm>
    using namespace std;
    
    int main()
    {
        int num;
        while (cin >> num)
        {
            vector<string> vect;
            string s;
            while (num--)
            {
                cin >> s;
                vect.push_back(s);
            }
            string query;
            cin >> query;
            string queryStr = query;
            sort(queryStr.begin(), queryStr.end());
            string temp;
            vector<string> res;
            for (vector<string>::iterator it = vect.begin(); it != vect.end(); ++it)
            {
                temp = *it;
                sort(temp.begin(), temp.end());
                if (temp == queryStr && *it != query)
                    res.push_back(*it);
            }
            sort(res.begin(), res.end());
            cout << res.size() << endl;
            int index;
            cin >> index;
            if (index <= res.size())
                cout << res[index - 1] << endl;
    
        }
    
        return 0;
    }