多行数据,每行为一个数字串。
保证数字串的总长度不超过1000,每行数据的答案至少有1个且不超过1000个。
多行数据,每行对应输出通过数字串破译得到的所有字符串,并按照字符串顺序排列,字符串之间用单个空格分隔。每行开头和结尾不允许有多余的空格。
1 12 123
a ab l abc aw lc
"""" 递归求解,一种变式DFS 对存在'0'的情况特殊处理 """ import sys def dfs(s, temp, ans): if not s: ans.append(''.join(temp)) return if (len(s) >= 2 and s[1] != '0') or len(s) == 1: dfs(s[1:], temp + (chr(int(s[0]) + ord('a') - 1),), ans) if (len(s) >= 3 and s[2] != '0' or len(s) == 2) and int(s[:2]) <= 26: dfs(s[2:], temp + (chr(int(s[:2]) + ord('a') - 1),), ans) if __name__ == "__main__": for line in sys.stdin: s = line.strip() ans = [] dfs(s, tuple(), ans) print(' '.join(ans))
import java.io.BufferedReader; import java.io.InputStreamReader; import java.io.IOException; public class Main { static StringBuilder ans = new StringBuilder(); public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String str; while((str = br.readLine()) != null){ int[] nums = new int[str.length()]; for(int i = 0; i < nums.length; i++){ nums[i] = str.charAt(i) - '0'; } dfs(nums, 0, new StringBuilder()); System.out.println(ans); ans = new StringBuilder(); } } private static void dfs(int[] nums, int index, StringBuilder sb) { if(index >= nums.length){ ans.append(sb).append(" "); // 翻译完了添加答案 }else{ // 如果单独出来个0,之前的决定有误,只考虑不为0的情况 if(nums[index] == 1){ // nums[index]翻译成一个字符 sb.append((char)('a' + nums[index] - 1)); dfs(nums, index + 1, sb); sb.deleteCharAt(sb.length() - 1); // nums[index]和nums[index+1]翻译成一个字符 if(index < nums.length - 1){ int offset = 10 * nums[index] + nums[index + 1]; sb.append((char)('a' + offset - 1)); dfs(nums, index + 2, sb); sb.deleteCharAt(sb.length() - 1); } }else if(nums[index] == 2){ // nums[index]翻译成一个字符 sb.append((char)('a' + nums[index] - 1)); dfs(nums, index + 1, sb); sb.deleteCharAt(sb.length() - 1); // nums[index]和nums[index+1]翻译成一个字符 if(index < nums.length - 1 && (0 <= nums[index + 1] && nums[index + 1] <= 6)){ int offset = 10 * nums[index] + nums[index + 1]; sb.append((char)('a' + offset - 1)); dfs(nums, index + 2, sb); sb.deleteCharAt(sb.length() - 1); } }else if(nums[index] >= 3){ sb.append((char)('a' + nums[index] - 1)); dfs(nums, index + 1, sb); sb.deleteCharAt(sb.length() - 1); } } } }
#include <bits/stdc++.h> using namespace std; int main(){ string s; vector <string> ver; auto solve = [&](auto& self, string use, string ret){ if(use.size() == 0){ ver.push_back(ret); return; } int t1 = (use[0] - '0'); if(t1 >= 1){ char ch1 = (t1 - 1) + 'a'; self(self, use.substr(1), ret + ch1); } if(use.length() >= 2){ int t2 = 10 * (use[0] - '0') + (use[1] - '0'); if(t2 >= 10 && t2 <= 26 ){ char ch2 = (t2 - 1) + 'a'; self(self, use.substr(2), ret + ch2); } } }; while(cin >> s){ ver.clear(); solve(solve, s, ""); for (auto ss : ver){ cout << ss << " "; } cout << "\n"; } return 0; }
import sys def game(s,cur): if not s: res.append(cur) else: i = 0 if s[i]=='1': game(s[i+1:],cur+dic[s[i]]) if i<len(s)-1: game(s[i+2:],cur+dic[s[i:i+2]]) elif s[i]=='2': game(s[i+1:],cur+dic[s[i]]) if i<len(s)-1 and int(s[i+1])<7: game(s[i+2:],cur+dic[s[i:i+2]]) elif s[i]=='0': return else: game(s[i+1:],cur+dic[s[i]]) if __name__=='__main__': dic = {} for i in range(1,27): dic[str(i)] = chr(i+96) for line in sys.stdin.readlines(): res = [] s = line.strip() game(s,'') res.sort() print(' '.join(res))
#include <bits/stdc++.h> using namespace std; string s; vector<string> v; int l; void DFS(string t, int p){ if(p==l){ v.push_back(t); return ; } char c = 'a'+s[p]-'1'; if(!(p+1<l && s[p+1]=='0')) //除了第二位0的情况 DFS(t+c, p+1); if(p+1<l && (s[p]=='1' || (s[p]=='2' && s[p+1]<='6'))){ if(!(p+2<l && s[p+2]=='0')){ c = 'a' + 10*(s[p]-'0') + (s[p+1]-'1'); DFS(t+c, p+2); } } } int main(){ while(cin>>s){ l = s.length(); v.clear(); string t=""; DFS(t,0); for(int i=0;i<v.size();i++){ if(i==v.size()-1) cout<<v[i]<<endl; else cout<<v[i]<<" "; } } return 0; }
由题意得可以一个一个的解码,也可以两个一组的解码,两者组合起来的情况有很多,是一种深度 的分情况的问题,所以自然就使用递归求解。 #include<iostream> #include<string> #include<vector> using namespace std; void get_all(string s,int i,string res,vector<string> &tmp) { if(i==s.size()-1) { res+=char((s[i]-48)+96); tmp.push_back(res); return; } if(i>s.size()-1) { tmp.push_back(res); return; } if((s[i]-48)*10+(s[i+1]-48)>26) { res+=char((s[i]-48)+96); get_all(s,i+1,res,tmp); } else{ string aux=res; res+=char((s[i]-48)+96); //判断s[i+1]是否为'0',如果是'0',则不能在当前位置一个一个的解码 if(s[i+1]!='0') get_all(s,i+1,res,tmp); res=aux+char(((s[i]-48)*10+(s[i+1]-48))+96); //下面是判断s[i+2]是否为'0',假如s[i+2]为'0',则我们在当前位置两个一组解码后会对'0'本身解码 //当i==s.size()-2时,i+2已经越界,所以要加一个判断 if(i==s.size()-2) get_all(s,i+2,res,tmp); else if(s[i+2]!='0') get_all(s,i+2,res,tmp); } } int main() { string s; while(cin>>s) { vector<string> tmp; get_all(s,0,"",tmp); for(int i=0;i<tmp.size();i++) { cout<<tmp[i]<<' '; } cout<<endl; } }
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String s; while((s = br.readLine()) != null){ int n = s.length(); int[] nums = new int[n]; for (int i = 0; i < n; i++) { nums[i] = s.charAt(i) - '0'; } StringBuilder res = new StringBuilder(); StringBuilder temp = new StringBuilder(); dfs(nums, 0, temp, res); System.out.println(res); } } public static void dfs(int[] nums, int index, StringBuilder temp, StringBuilder res) { if (index >= nums.length) { res.append(temp).append(" "); return; } if (nums[index] != 0) { char c = (char) ('a' + nums[index] - 1); temp.append(c); dfs(nums, index + 1, temp, res); temp.deleteCharAt(temp.length() - 1); } if (index >= nums.length - 1) return; int offset = nums[index] * 10 + nums[index + 1]; if (offset >= 10 && offset <= 26) { char c = (char) ('a' + offset - 1); temp.append(c); dfs(nums, index + 2, temp, res); temp.deleteCharAt(temp.length() - 1); } } }
import java.io.*; import java.lang.*; public class Main { private static StringBuilder sb; private static BufferedReader br = new BufferedReader( new InputStreamReader(System.in)); private static String nextString() { try { return br.readLine(); }catch(IOException e) { throw new RuntimeException(e); } } public static void main(String[] args) { String s; while((s = nextString()) != null) { solution(s); } } private static void solution(String str) { sb = new StringBuilder(); StringBuilder cur = new StringBuilder(); dfs(str, cur, 0); System.out.println(sb.toString().trim()); } private static void dfs(String str, StringBuilder cur, int index) { //两个递归结束条件:成功破译和非成功破译 if(index == str.length()) { sb.append(" "); sb.append(cur); return; }else if((index + 1 == str.length()) && (str.charAt(index) == 0)) { return;//无法成功破译,无法加到sb中 } if(str.charAt(index) != '0'){//一个字符 cur.append((char)(str.charAt(index)-'1' + 'a')); dfs(str, cur, index + 1); cur.delete(cur.length() - 1, cur.length()); if(index + 2 <= str.length()) {//两个字符 int tmp = Integer.parseInt(str.substring(index, index + 2)); if(tmp >= 10 && tmp <= 26) { cur.append((char)(tmp - 1 + 'a')); dfs(str, cur, index + 2); cur.delete(cur.length() - 1, cur.length()); } } } } }
import java.io.InputStreamReader; import java.io.BufferedReader; import java.io.IOException; import java.util.ArrayList; import java.util.List; public class Main{ final static char[] RECORD = new char[]{ ' ','a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p', 'q','r','s','t','u','v','w','x','y','z' }; static StringBuilder res; public static void main(String[] args) throws IOException{ BufferedReader bf = new BufferedReader(new InputStreamReader(System.in)); while(bf.ready()){ String number = bf.readLine(); res = new StringBuilder(); dfs(number.toCharArray(),0,new StringBuilder(),false); System.out.println(res.toString().trim()); } } private static void dfs(char[] sArr,int start,StringBuilder track,boolean flag){ if(start == sArr.length){ res.append(track.toString()); res.append(" "); return; } if(sArr[start]>'0' && sArr[start]<='9'){ dfs(sArr,start+1,new StringBuilder(track).append(RECORD[sArr[start]-'0']),false); } if(!flag && start>0 && (sArr[start-1] == '1' || (sArr[start-1] == '2' && sArr[start]<='6'))){ StringBuilder copy = new StringBuilder(track); copy.deleteCharAt(copy.length()-1); int RIndex = (sArr[start-1]-'0')*10+(sArr[start]-'0'); copy.append(RECORD[RIndex]); dfs(sArr,start+1,copy,true); } } }
#include<iostream> #include<vector> #include<string> using namespace std; class deCode { vector<string> vec; int strLen; string str; const char base = 'a' - 1; public: deCode(void) = delete; deCode(string& strIn):str(strIn) { strLen = str.length(); string curStr; getSolve(0,curStr); } void disp(void); void getSolve(int pos, string& curStr); }; void deCode::getSolve(int pos, string& curStr) { if(pos >= strLen) { vec.push_back(curStr); return; } if(!(pos < strLen-1 && str[pos+1] == '0'))//防止10的情况 { curStr.push_back(str[pos] - '0' + base); getSolve(pos+1,curStr); curStr.pop_back(); } if(pos < strLen-1 && (str[pos] == '1' || (str[pos] == '2' && str[pos+1] <'7'))) { if(!(pos < strLen-2 && str[pos+2] == '0'))//防止120的情况 { int bias = (str[pos] - '0')*10 + str[pos+1] - '0'; curStr.push_back(bias + base); getSolve(pos+2,curStr); curStr.pop_back(); } } } void deCode::disp(void) { int len = vec.size(); for(int i=0;i<len-1;i++) cout<<vec[i]<<' '; cout<<vec[len-1]<<endl; } int main(void) { string str; while(cin>>str) { deCode dd(str); dd.disp(); } return 0; }
#include<bits/stdc++.h> using namespace std; void dfs(string s,int cur,string& tmp,vector<string>& ans) { if(cur==s.size()) { ans.push_back(tmp); return; } // 当前遇到0 返回 if(s[cur]=='0') return; // 单字符破译 tmp.push_back('a'+s[cur]-'0'-1); dfs(s,cur+1,tmp,ans); tmp.pop_back(); if(cur+1<s.size()) { int idx = (s[cur]-'0')*10+s[cur+1]-'0'; // 双字符组合破译 if(idx<=26) { tmp.push_back('a'+idx-1); dfs(s,cur+2,tmp,ans); tmp.pop_back(); } } } int main() { string s; while(cin>>s) { string tmp = ""; vector<string>v; dfs(s,0,tmp,v); for(auto t:v) cout<<t<<" "; cout<<endl; } return 0; }
#include<iostream> (720)#include<string> #include<set> using namespace std; set<string> st; void BackTrack(string &num, string &temp, int k){ if (k == num.size()){ st.insert(temp); return ; } if (num[k] == '1'){ temp.push_back(num[k]-'1'+'a'); BackTrack(num, temp, k+1); temp.pop_back(); if (k < num.size()-1){ int t = stoi(num.substr(k,2)); temp.push_back('a' + t - 1); BackTrack(num, temp, k+2); temp.pop_back(); } } else if (num[k] == '2'){ temp.push_back(num[k]-'1'+'a'); BackTrack(num, temp, k+1); temp.pop_back(); if (k < num.size()-1 && stoi(num.substr(k,2)) <= 26){ int t = stoi(num.substr(k,2)); temp.push_back('a' + t - 1); BackTrack(num, temp, k+2); temp.pop_back(); } } else if(num[k] != '0'){ temp.push_back(num[k]-'1'+'a'); BackTrack(num, temp, k+1); temp.pop_back(); } return ; } int main(void){ char s[1000]; while (scanf("%s", s) == 1){ string num(s); string temp; st.clear(); BackTrack(num, temp, 0); for (auto it = st.begin(); it != st.end(); it++){ cout<<*it<<" "; } cout<<endl; } return 0; }
import java.util.ArrayList; import java.util.Scanner; /** * @Date: 2020-05-04 21:53 * @version: 1.0 */ public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); String str; int nums[]; while (sc.hasNextLine()){ str = sc.nextLine(); nums = new int[str.length()]; for (int i = 0; i < str.length(); i++) nums[i] = str.charAt(i)-'0'; ArrayList<StringBuilder> arr = new ArrayList<>(); dfs(nums, 0, arr, new StringBuilder()); int i = 0; for (; i < arr.size()-1; i++) System.out.print(arr.get(i)+" "); System.out.println(arr.get(i)); } } private static void dfs(int nums[], int i, ArrayList<StringBuilder> arr, StringBuilder sb) { if (i == nums.length){ arr.add(new StringBuilder(sb)); return; } if (nums[i]==0) return; sb.append((char)(nums[i]-1+'a')); h(nums, i+1, arr, sb); sb.deleteCharAt(sb.length()-1); if (i+1<nums.length&&(nums[i]==1||(nums[i]==2&&nums[i+1]<=6))){ sb.append((char)(nums[i]*10+nums[i+1]-1+'a')); h(nums, i+2, arr, sb); sb.deleteCharAt(sb.length()-1); } } }
while True: try: ss = input() def dfs(ss,tmp,ts,ans): if not ss: ans.append(ts) return ans for i in range(1,3): if len(ss)-i>=0: tmp = ss[0:i] if int(tmp)<=26 and int(tmp)>0 and tmp[0]!='0' : ts= ts+'*'+tmp dfs(ss[i:],tmp,ts,ans) ts = ts[:-2] return ans ans = dfs(ss,'','',[]) last =[] for d in ans: s = d.replace('*',' ').strip() nums = s.split() res = [] for i in range(len(nums)): res.append(chr(int(nums[i])-1+ord('a'))) last.append(res) ans =[] for d in last: ans.append(''.join(d)) print(' '.join(ans)) except: break
import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); while (sc.hasNext()) { char[] s = sc.next().toCharArray(); if(s.length == 1) { System.out.println(parse(s[0])); continue; } List<String> lst = new ArrayList<>(); char[] dst = new char[s.length * 2]; dfs(s, 0, dst, 0, lst); for (String str : lst) { System.out.print(str); System.out.print(" "); } System.out.println(); } } private static void dfs(char[] src, int idx, char[] dst, int dstIdx, List<String> result) { if(src.length == idx) { result.add(new String(dst, 0, dstIdx)); return; } char a = src[idx]; if(a == '0') { return; } dst[dstIdx] = parse(a); dfs(src, idx + 1, dst, dstIdx + 1, result); if(idx + 1 < src.length) { char b = src[idx + 1]; char tb = parse(a, b); if (tb > 'z' || tb < 'a') { return; } dst[dstIdx] = tb; dfs(src, idx + 2, dst, dstIdx + 1, result); } } private static char parse(char n1) { return (char)('a' + n1 - '0' - 1); } private static char parse(char n1, char n2) { int n = (n1 - '0') * 10 + n2 - '0'; return (char)(n + 'a' - 1); } }
/*回溯法,这里注意的一个小坑是a排在1而不是0*/ #include <iostream> #include <istream> #include <string> using namespace std; string input; bool isfirst = true; void dfs(string& ans, int n, int p, bool& isfirst){ if(p>=n){ if(isfirst){ isfirst = false; cout << ans; } else{ cout << " " << ans; } return; } if(p<n){ if(input[p] == '0'){ return; } ans += input[p]-'1'+'a'; dfs(ans, n, p+1, isfirst); ans.erase(ans.size()-1); if(p+1<n && 10*(input[p]-'0')+input[p+1]-'0' <= 26){ ans += 10*(input[p]-'0')+input[p+1]-'0' -1 + 'a'; dfs(ans, n, p+2, isfirst); ans.erase(ans.size()-1); } } } int main(){ while(cin >> input){ int n = input.size(); string ans = ""; isfirst = true; dfs(ans, n, 0, isfirst); cout << endl; } return 0; }
def func(nn, res, lst): if len(nn) == 0: if res not in lst: lst.append(res) return for i in range(len(nn)): if nn[i] == "1" and i+1 < len(nn): if nn[i+1] == "0": func(nn[i+2:], res+num_to_char(nn[i:i+2]), lst) return else: if i+2 < len(nn) and nn[i+2] == "0": func(nn[i+1:], res+num_to_char(nn[i]), lst) return else: func(nn[i+1:], res+num_to_char(nn[i]), lst) func(nn[i+2:], res+num_to_char(nn[i:i+2]), lst) return elif nn[i] == "2" and i+1<len(nn) and int(nn[i+1]) <= 6: if nn[i+1] == "0": func(nn[i+2:], res+num_to_char(nn[i:i+2]), lst) return else: if i+2<len(nn) and nn[i+2] == "0": func(nn[i+1:], res+num_to_char(nn[i]), lst) return else: func(nn[i+1:], res+num_to_char(nn[i]), lst) func(nn[i+2:], res+num_to_char(nn[i:i+2]), lst) return else: res += num_to_char(nn[i]) if res not in lst: lst.append(res) def num_to_char(num_str): return chr(int(num_str) + 96) while True: try: nn = input() res = "" lst = [] func(nn, res, lst) lst.sort() for per_str in lst: print(per_str, end=" ") print() except: break