题目难度:二星
考察点:字符串、模拟
方法:模拟
1.分析:
根据题意,我们可以对这n个字符串进行枚举,即判断字符串两两是否有重复的字符,如果没有就计算两个字符串的长度乘积,将n^2个字符串的长度乘积求出来,然后比较输出最大值即可。有几个小坑点:
(1). 处理输入问题,因为这个题的输入是比较恶心的,所以我们需要专门的处理一下输入,即输入的是一个字符串,然后将""之内的字符串全部提取出来,保存在一个vector数组中,具体可以详见代码。
(2). 判断s1,s2两个字符串是否有重复字符,那么我们可以首先定义一个标志数组ok[26] ,然后对s1进行遍历,ok[s1[i]-'a'] = true;, 然后在对s2进行遍历,如果在s2中找到有相同字符即ok[s2[i]-'a'] = true;的话直接return 0,否则继续往下进行遍历,直到s2的字符全部遍历完毕,发现没有相同字符,return s1和s2的字符串长度之积。
举个例子: 有两个字符串s1 = "abc", s2 = "dea"
在对s1遍历完毕之后,那么在ok数组中的表示就是ok[0] = ok[1] = ok[2] = true,其余的都是false,然后在对s2进行遍历:
当遍历到第一个字符d时,发现ok['d'-'a'=3] = false,那么继续往下遍历,
当遍历到第一个字符d时,发现ok['d'-'a'=3] = false,那么继续往下遍历,
当遍历到第二个字符d时,发现ok['e'-'a'=4] = false,那么继续往下遍历,
当遍历到最后一个字符d时,发现ok['a'-'a'=0] = true,那么有相同字符,直接return 0。
(1). 输入字符串s
(2). 将字符串s进行处理,得到一个包含所有字符串的vector<string> a;
(3). 按照上述算法进行遍历,即i从1-n, j从1-n,得到两个字符串s[i]和s[j]的字符串长度之积,如果有相同字符,长度之积为0.,并比较最大值。
(4). 输出最大的字符串长度之积结果为ans。
2.复杂度分析:
时间复杂度:O(n^2)空间复杂度:O(26)
3.代码:
#include <bits/stdc++.h> using namespace std; typedef long long LL; const int MAXN = 1e6+5; vector<string> get_vector(string s) { int i = 0, n = s.size(); vector<string> ans; while(i < n) { if(i<n && s[i++]=='"') { string tmp = ""; while(i<n && s[i]!='"') tmp += s[i++]; ans.push_back(tmp); i++; } } return ans; } bool ok[26]; int get_ans(string s1, string s2) { memset(ok, false, sizeof ok); for(int i=0; i<s1.size(); i++) ok[s1[i]-'a'] = true; for(int i=0; i<s2.size(); i++) if(ok[s2[i]-'a']) return 0; return s1.size() * s2.size(); } int main() { string s; cin>>s; vector<string> a = get_vector(s); int ans = 0; for(int i=0; i<a.size(); i++) { for(int j=0; j<a.size(); j++) { ans = max(ans, get_ans(a[i], a[j])); } } cout<<ans<<endl; return 0; }