题目难度:1星
考察点:组合数学
方法:组合数学
1. 分析
我们分析一下题意,其实这个题就是求给定一个只包含小写字母的字符串,然后在加入一个新的小写字母,看能够组成多少种不同的字符串?这个题我们可以借助高中时候学习的插空法,假设字符串的长度为n,那么就有n+1个空,每个空都有26种(小写字母有26个)选择,所以一共有(n+1)26种方法,但是这些字符串种可能有重复的,所以接下来就是计算重复的字符串个数。这个其实也很容易,对于插入的新字符如果有跟原有字符串s相同的字符,那么此时插入的字符放在前后都是一样的了,所以只需要在原有的计算结果上减掉字符串长度即可,即ans = (n+1)26-n。举个例子:
对于字符串"ab"来说,有三个空记作空0,空1,空2,那么插入的字符也只考虑a和b(因为其它的一定不会有重复,没有必要进行考虑)
空0填a:aab ==》重复
空1填a:aab ==》重复
空2填a:aba
空0填b:bab
空1填b:abb ==》重复
空2填b:abb ==》重复
所以我们需要剪掉字符串的长度。
算法实现:
(1). 输入字符串s
(2). 根据上述公式计算ans=(s.size()+1)*26-s.size()
(2). 输出答案ans。
2. 复杂度分析:
时间复杂度:O(n),计算字符串的长度是O(n)的算法。 空间复杂度:O(1)
3. 代码:
#include <bits/stdc++.h> using namespace std; int main() { string s; cin>>s; cout<<(s.size()+1)*26-s.size()<<endl; return 0; }