回溯生成所有的LuckyString，計(jì)數(shù)即可。10!*26操作數(shù)。在tc上不會(huì)超時(shí)。
看Summary中很多人用next_permutation生成所有全排列再判斷是否為L(zhǎng)uckyString，這樣更快更方便一些。
???class?TheLuckyString
??????????????{?
??????????????public:?
??????????????????int?len;
??????????????????int?res;
??????????????????int?cnt[26];
??????????????????int?last;
??????????????????int?visited[11];
??????????????int?count(string?s)?
??????????????????{?????????????????????????
????????????????????????memset(cnt,0,sizeof(cnt));
????????????????????????len?=?s.size();
????????????????????????res?=?0;
????????????????????????for(int?i=0;i<s.size();++i)
????????????????????????????cnt[s[i]-'a']++;
????????????????????????int?len?=?s.size();
????????????????????????bt();
????????????????????????return?res;
????????????????????????return?0;
??????????????????}?
??????????????void?bt(){
??????????????????for(int?i=0;i<26;++i){
??????????????????????if(cnt[i]!=0){
??????????????????????????visited[0]=i;
??????????????????????????cnt[i]--;
??????????????????????????_bt(1);
??????????????????????????cnt[i]++;
??????????????????????}
??????????????????}
??????????????}
??????????????void?_bt(int?depth){
??????????????????if(depth==len){
????????????????????res++;
????????????????????return;
??????????????????}??????????????????
??????????????????????for(int?i=0;i<26;++i){
??????????????????????????if(cnt[i]!=0){
??????????????????????????????if(i==visited[depth-1])
??????????????????????????????????continue;
????????????????????????????visited[depth]?=?i;
????????????????????????????cnt[i]--;
????????????????????????????_bt(depth+1);
????????????????????????????cnt[i]++;
??????????????????????????}
??????????????????????}
??????????????}
｝
next_permutation解：
???class?TheLuckyString
??????????????{?
??????????????public:?
??????????????int?count(string?s)?
??????????????????{?????????????????????????
??????????????????int?res?=?0;
??????????????????sort(s.begin(),s.end());
??????????????????do{
??????????????????????bool?ok?=?true;
??????????????????????for(int?i=0;i+1<s.size();++i){
??????????????????????????if(s[i]==s[i+1]){
??????????????????????????????ok?=?false;
??????????????????????????????break;
??????????????????????????}
??????????????????????}
??????????????????????
??????????????????????if(ok)
????????????????????????res++;
??????????????????}while(?next_permutation(s.begin(),s.end())?);
????????????????????return?res;
??????????????????}
????????????? }