P9364 Perfect Word 题解

Infinity_Fantasy · 2023-10-12 21:46:00 · 题解

思考

经过思考之后发现，完美单词只能是已给出的，那这样的话题目就转化成了求已给单词满足条件的最大长度。

构思

既然这样，我们不妨用一个 map 来映射出每个单词是否有出现，然后从大到小排序，用贪心的思想，依次排查，可以暴力判每一个字符串。

单次复杂度分析：

在这段代码中，有两个嵌套的循环。外层循环是从 0 到 s.size()-1 的 for 循环，它迭代了字符串 s 的每个字符，因此它的时间复杂度是 O(n)。

内层循环也是一个 for 循环，当字符串满足条件时，它迭代了所有可能的子串长度 len。对于每个字符 i，内层循环的循环次数是从 1 到 n-i，因此内层循环的时间复杂度是 O(n-i)。

将内层循环的时间复杂度进行累加，得到总的时间复杂度：

但是如果是不满足条件的字符串即中途退出的情况，最好的复杂度是 O(1)，最坏的情况仍是 O(n^2) 的。

综上所述，整体的复杂度应为 O(n^2)。

代码

#include<bits/stdc++.h>
using namespace std;
int n;
string s[100005];
map<string,bool> mp;
bool check(string s){
    for(int i=0;i<s.size();i++)
        for(int len=1;len+i-1<s.size();len++)
            if(!mp[s.substr(i,len)]) return false;
    return true;
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++) cin>>s[i],mp[s[i]]=1;
    sort(s+1,s+1+n,[](string a,string b){return (int)a.size()>(int)b.size();});
    for(int i=1;i<=n;i++)
        if(check(s[i])){
            cout<<s[i].size();
            break;
        }
    return 0;
}

小笔记：

substr 函数的用法：name.substr(i,len) 表示的是从 name 中截取一段字符串其下标从 i 开始往后数 len 个字符。