算法-数字字符转化为字母字符种数

2022-4-22 diaba 算法 

package com.jiucaiyuan.net.question;

/**
 * 【问题】规定1和A对应，2和B对应，3和C对应...
 * 那么一个数字字符串，比如"111"，可以转化为"AAA","KA","AK"
 * 给定一个只有数字字符组成的字符串str，返回有多少种转化结果
 *
 * @Author jiucaiyuan  2022/4/22 23:02
 * @mail services@jiucaiyuan.net
 */
public class ConvertNum2Letters {
    public static int number(String str) {
        if (str == null) {
            return 0;
        }
        return process(str.toCharArray(), 0);
    }

    /**
     * i之前（0~i-1）位置已经分析过，当前方法分析i位置及以后
     *
     * @param chs 给定的数字字符串
     * @param i   当前i位置及以后有多少种
     * @return 返回转化种数
     */
    public static int process(char[] chs, int i) {
        if (i == chs.length) {
            return 1;
        }
        //当前位置为0，无法对应到什么字符，说明之前的安排是不可取的，返回0种
        if (chs[i] == '0') {
            return 0;
        }

        if (chs[i] == '1') {
            //尝试i自己转化为一个字符，后面有多少种
            int res = process(chs, i + 1);
            //如果i+1后还存在字符，尝试i和i+1组合转化，后面有多少种
            if (i + 1 < chs.length) {
                res += process(chs, i + 2);
            }
            return res;
        }
        if (chs[i] == '2') {
            //尝试i自己转化为一个字符，后面有多少种
            int res = process(chs, i + 1);
            //如果i和i+1一起组合，并且没有超过26，后面有多少种
            if (i + 1 < chs.length && chs[i + 1] >= '0' && chs[i + 1] <= '6') {
                res += process(chs, i + 2);
            }
            return res;
        }
        //如果当前字符是3~9，只能i自己进行转化，后面是i+1及以后有多少种
        return process(chs, i + 1);
    }

    public static void main(String[] args) {
        System.out.println(number("111"));
    }
}

« 算法-Manacher算法（最长回文子串、回文半径） | 算法-不用额外空间逆序栈»

发表评论：

Powered by emlog 京ICP备15045175号-1 Copyright © 2022