解码字符串的几种方法？ [英] number of ways to decode a string?

问题描述

我正在处理需要解码字符串的问题。

I am working on problem where I need to decode a string..

一条包含AZ字母的消息被编码为数字
使用以下映射：

A message containing letters from A-Z is being encoded to numbers using the following mapping:

'A'-> 1

'B'-> 2

...

'Z'-> 26

给出一个仅包含数字的非空字符串，确定总共
种解码方式。

Given a non-empty string containing only digits, determine the total number of ways to decode it.

示例1：

输入： 12

输出：2

说明：可以将其解码为 AB（1 2）或 L（12）。

Explanation: It could be decoded as "AB" (1 2) or "L" (12).

示例2：

输入： 226

输出：3

说明：可以将其解码为 BZ（2 26）， VF（22 6）或 BBF（2 2 6）。

Explanation: It could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6).

I提出了以下递归方法，但此输入 227给出错误的输出。输出应为 2，但我的程序给出的是 3：

I came up with below recursion approach but it is giving wrong output for this input "227". Output should be "2" but my program is giving "3":

  public static int decodeWays(String data) {
    return helper(data, data.length());
  }

  private static int helper(String data, int k) {
    if (k == 0)
      return 1;
    int s = data.length() - k;
    if (data.charAt(s) == '0')
      return 0;

    int result = helper(data, k - 1);
    if (k >= 2 && Integer.parseInt(data.substring(0, 2)) <= 26) {
      result += helper(data, k - 2);
    }
    return result;
  }

上述方法有什么问题？

推荐答案

在此行-

if (k >= 2 && Integer.parseInt(data.substring(0, 2)) <= 26) {

您始终检查相同的2位数字 data.substring（0，2）。而是考虑类似

You always check the same 2-digit number data.substring(0, 2). Instead consider something like

data.substring(data.length()-k, data.length()).substring(0, 2)

或

data.substring(data.length()-k, data.length()-k+2)

这篇关于解码字符串的几种方法？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！