首页 > 试题广场 >

密码破译

[编程题]密码破译
  • 热度指数：2668 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 64M，其他语言128M
  • 算法知识视频讲解
我们来做一个简单的密码破译游戏。破译的规则很简单，将数字转换为字母，1转化为a，2转化为b，依此类推，26转化为z。现在输入的密码是一串数字，输出的破译结果是该数字串通过转换规则所能产生的所有字符串。

输入描述:
多行数据，每行为一个数字串。
保证数字串的总长度不超过1000，每行数据的答案至少有1个且不超过1000个。


输出描述:
多行数据，每行对应输出通过数字串破译得到的所有字符串，并按照字符串顺序排列，字符串之间用单个空格分隔。每行开头和结尾不允许有多余的空格。
示例1

输入

1
12
123

输出

a
ab l
abc aw lc
算法知识视频讲解
添加回答
Java
北极以北_头像 北极以北_
DFS 
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);
        }
    }
    

}


发表于 2022-09-11 18:43:09 回复(0)
Java
pein531头像 pein531

深度优先搜索

既然是要输出所有的翻译结果，那肯定就支持暴力的DFS了。果不其然，数据量很小，直接从index=0位置进行递归求解：
  1. 如果当前位置是1，尝试当前位置单独翻译成字母a，或者在还有下一个数字的情况下与下一个数字联合翻译成j~s的字母；
  2. 如果当前位置是2，尝试当前位置单独翻译成字母b，或者在还有下一个数字的情况下与下一个数字联合翻译成t~z的字母；
  3. 如果当前位置是大于2的数字，则单独将当前数字翻译成c~i的字母；
  4. 如果当前位置是0，说明之前的翻译有误，这个0本应和前一个数字结合，但本轮深搜并没有这么做，搜索无效。 
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);
            }
        }
    }
}

发表于 2022-01-13 10:59:50 回复(0)
Java
科大15届软工代言人头像 科大15届软工代言人 
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());
                }
            }
        }
    }
}

发表于 2021-08-27 10:10:15 回复(0)
Java
再向前一点头像 再向前一点 
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);
        }
    }
}

发表于 2021-08-25 10:35:13 回复(0)
提交观点

问题信息

iOS工程师 动态规划 小米集团 字符串 模拟 穷举 2019
来自：小米2019秋招iOS...
上传者：小小
难度：
5条回答 6595浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号