c077 - 00417 - Word Index
題目描述
題目要求將符合特定規則的字串轉換為唯一的整數編號。規則是字串中的每個字元都必須大於前一個字元（字典序）。如果字串不符合此規則，則輸出 0。否則，輸出對應的編號。編號的產生方式是根據字串長度和字元順序進行的，例如 a -> 1, b -> 2, ab -> 27, ac -> 28。
解題思路
程式碼首先預先計算所有符合規則的字串的編號，並將它們儲存在一個 map 中。然後，對於每個輸入字串，程式碼檢查它是否在 map 中。如果在，則輸出對應的編號；否則，輸出 0。預計算所有可能的字串的編號是解決這個問題的關鍵。由於字串長度限制為 5，且字元是小寫字母，因此可以通過嵌套迴圈生成所有可能的字串，並計算它們的編號。
複雜度分析
- 時間複雜度: O(1) (對於每個輸入字串的查詢) + O(N) (預計算所有字串的編號，其中 N 是所有有效字串的數量，在題目限制下是一個常數)。整體來說，可以視為 O(1)。
- 空間複雜度: O(N) (儲存所有有效字串及其編號的 map，其中 N 是所有有效字串的數量，在題目限制下是一個常數)。整體來說，可以視為 O(1)。
程式碼
#include <bits/stdc++.h>
using namespace std;
int n,ct;
map <string,int> mp;
string s;
int main(){
cin.tie(0); ios::sync_with_stdio(0);
for(int i=0;i<27;++i)
for(int j=(i==0?0:i+1);j<27;++j)
for(int k=(j==0?0:j+1);k<27;++k)
for(int l=(k==0?0:k+1);l<27;++l)
for(int m=(l==0?0:l+1);m<27;++m){
string tmp;
if(i)tmp+='a'+i-1;
if(j)tmp+='a'+j-1;
if(k)tmp+='a'+k-1;
if(l)tmp+='a'+l-1;
if(m)tmp+='a'+m-1;
mp[tmp]=ct++;
}
while(cin >> s){
if(mp.find(s)==mp.end()){
cout << "0\n";
continue;
}
cout << mp[s] << "\n";
}
}