密码破译

""""
递归求解，一种变式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);
            }
        }
    }
}

dfs求解问题。

需要注意此题需要分成3种情况：
1.当前处理位置之后的第二位为0， 如120。
此时只能翻译1，不能翻译12，否则剩下的0无法翻译。

2.当前处理位置之后的第一位为0， 如102。
此时只能翻译10，不能只翻译1，否则剩下的0无法翻译。

3.当前处理位置之后的两位都不为0，如123。
此时既可翻译1，也可翻译12。

#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;
}	

#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.*;
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.*;

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