华为机试真题 C++ 实现【真正的密码】【2022.11 Q4 新题】

题目

在一行中输入一个字符串数组，如果其中一个字符串的所有以索引0开头的子串在数组中都有，那么这个字符串就是潜在密码，在所有潜在密码中最长的是真正的密码，如果有多个长度相同的真正的密码，那么取字典序最大的为唯一的真正的密码，求唯一的真正的密码。

示例1：

输入： h he hel hell hello o ok n ni nin ninj ninja

输出： ninja

说明：
按要求，hello、ok、ninja都是潜在密码。检查长度，hello、ninja是真正的密码。检查字典序，ninja是唯一真正密码。

示例2：

输入： a b c d f

输出： f

说明： 按要求，a b c d f 都是潜在密码。检查长度，a b c d f 是真正的密码。检查字典序，f是唯一真正密码。

代码：

#include <iostream>
#include <string>
#include <map>
#include <set>
#include <vector>
#include <algorithm>
#include <numeric>

using namespace std;
bool cmp(string str1, string str2)
{
	if (str1.size() != str2.size())
	{
		return str1.size() > str2.size();
	}
	else
	{
		return str1 > str2;
	}
}

int main()
{
	int left = 0, right = 0;
	//string ans;
	string str;
	vector<string> vec;
	vector<string> ans;

	while (cin >> str)
	{
		if (find(vec.begin(), vec.end(), str) == vec.end())
		{
			vec.push_back(str);
		}
	}
	sort(vec.begin(), vec.end());

	for (int i = vec.size() - 1; i >= 0; --i)
	{
		string str1 = vec.at(i);
		bool flag = true;
		for (int j = 0; j < str1.size(); ++j)
		{
			string str2 = str1.substr(0, j + 1);
			if (find(vec.begin(), vec.end(), str2) == vec.end())
			{
				flag = false;
				break;
			}
		}
		if (flag)
		{
			ans.push_back(str1);
		}
		
	}

	sort(ans.begin(), ans.end(), cmp);

	cout << *(ans.begin()) << endl;
	return 0;
}