題目描述
活字印刷術是中國古代四大發明之一，今天我們要試著用計算機實現一個“活字印刷術”。現在輸入一個字符串s,代表一套活字字模，其中每個字模上都刻有一個字母 s[i]。輸出你可以印出的非空字母序列的數目。
輸入
輸入數據由多組測試數據組成。每組測試數據第一行輸入一個字符串s ( 1 <= s.length <= 10 ），s中所有字母均為大寫字母
輸出
輸出可以印出的非空字母序列數目

樣例輸入 Copy

AAB

樣例輸出 Copy

8

提示

對于樣例：
可能的序列為 “A”, “B”, “AA”, “AB”, “BA”, “AAB”, “ABA”, “BAA”。

**

• 思路
• 這題看著很難，其實是計算無重復子序列
• 可以先用桶排序把字符串的字符記錄下來
• 每次for ‘A’到‘Z’如果有值就dfs，可以肯定每次dfs都是不會重復的，ans++

**

AC代碼

#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> using namespace std; int ans=0; int cnt[200]; string s; void dfs(int len){if(len==s.size())return ;//長度到頭了就結束了 for(int i=0;i<100;i++){//ascll碼 if(cnt[i]==0)continue;//沒有就跳過 cnt[i]--;ans++;dfs(len+1);//長度 +1cnt[i]++;//回溯 } } int main(){/* 活字印刷 */while(cin>>s){ memset(cnt,0,sizeof(cnt));int len=s.size();for(int i=0;i<len;i++){cnt[s[i]]++;//桶排序 }ans=0;dfs(0);cout<< ans <<endl;}return 0; }

總結

以上是生活随笔為你收集整理的活字印刷（dfs）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。