Ggthjy

Should we avoid writing fiction about historical events without extensive research?

How to mitigate "bandwagon attacking" from players?

Giving a talk in my old university, how prominently should I tell students my salary?

Why won't the strings command stop?

How can neutral atoms have exactly zero electric field when there is a difference in the positions of the charges?

How to get the first element while continue streaming?

Is there a full canon version of Tyrion's jackass/honeycomb joke?

Book about a time-travel war fought by computers

PTIJ: What’s wrong with eating meat and couscous?

How can I be pwned if I'm not registered on the compromised site?

How to merge row in the first column in LaTeX

How do you say “my friend is throwing a party, do you wanna come?” in german

Lock enemy's y-axis when using Vector3.MoveTowards to follow the player

What is the meaning of "notice to quit at once" and "Lotty points”

What is a term for a function that when called repeatedly, has the same effect as calling once?

Can I cast a spell through the Invoke Duplicity clone while inside a Forcecage?

Wardrobe above a wall with fuse boxes

Misplaced tyre lever - alternatives?

Can the Shape Water Cantrip be used to manipulate blood?

How can I highlight parts in a screenshot

Relationship between the symmetry number of a molecule as used in rotational spectroscopy and point group

Sometimes a banana is just a banana

Why would the IRS ask for birth certificates or even audit a small tax return?

“I had a flat in the centre of town, but I didn’t like living there, so …”

Counting the number of ways to decode a string

Google Code jam puzzle - Welcome to Code JamMystery sum with placeholder digitsComparing two strings to see if string 2 is inside string 1HackerRank NCR codesprint: Spiral MessageLeetcode 17. Letter Combinations of a Phone NumberHackerrank: Prefix neighborsFinding unique pairs in lottery ticketsFinding the lowest possible number of changes to turn one string into anotherHacker Rank Challenge : Find count of substrings which are special palindromeFinding all possible letter combinations from an inputted phone number

1

$begingroup$

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

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.

Example 1:

Input: "12"

Output: 2

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

Example 2:

Input: "226"

Output: 3

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

I came up with below recursion approach and it works fine. Is there any better or efficient way to solve the same problem?

  public static int decode(String data) {

    int[] memo = new int[data.length() + 1];

    return helper(data, data.length(), memo);

  }



  private static int helper(String data, int k, int[] memo) {

    if (k == 0)

      return 1;

    int s = data.length() - k;

    if (data.charAt(s) == '0')

      return 0;

    if (memo[k] != 0) {

      return memo[k];

    }



    int result = helper(data, k - 1, memo);

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

      result += helper(data, k - 2, memo);

    }

    memo[k] = result;

    return result;

  }

java algorithm recursion dynamic-programming

share|improve this question

edited 12 mins ago

200_success

130k16153417

asked 26 mins ago

user5447339user5447339

163110

$endgroup$

add a comment | 

1

$begingroup$

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

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.

Example 1:

Input: "12"

Output: 2

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

Example 2:

Input: "226"

Output: 3

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

I came up with below recursion approach and it works fine. Is there any better or efficient way to solve the same problem?

  public static int decode(String data) {

    int[] memo = new int[data.length() + 1];

    return helper(data, data.length(), memo);

  }



  private static int helper(String data, int k, int[] memo) {

    if (k == 0)

      return 1;

    int s = data.length() - k;

    if (data.charAt(s) == '0')

      return 0;

    if (memo[k] != 0) {

      return memo[k];

    }



    int result = helper(data, k - 1, memo);

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

      result += helper(data, k - 2, memo);

    }

    memo[k] = result;

    return result;

  }

java algorithm recursion dynamic-programming

share|improve this question

edited 12 mins ago

200_success

130k16153417

asked 26 mins ago

user5447339user5447339

163110

$endgroup$

add a comment | 

$begingroup$

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

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.

Example 1:

Input: "12"

Output: 2

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

Example 2:

Input: "226"

Output: 3

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

I came up with below recursion approach and it works fine. Is there any better or efficient way to solve the same problem?

  public static int decode(String data) {

    int[] memo = new int[data.length() + 1];

    return helper(data, data.length(), memo);

  }



  private static int helper(String data, int k, int[] memo) {

    if (k == 0)

      return 1;

    int s = data.length() - k;

    if (data.charAt(s) == '0')

      return 0;

    if (memo[k] != 0) {

      return memo[k];

    }



    int result = helper(data, k - 1, memo);

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

      result += helper(data, k - 2, memo);

    }

    memo[k] = result;

    return result;

  }

java algorithm recursion dynamic-programming

share|improve this question

edited 12 mins ago

200_success

130k16153417

asked 26 mins ago

user5447339user5447339

163110

$endgroup$

  public static int decode(String data) {

    int[] memo = new int[data.length() + 1];

    return helper(data, data.length(), memo);

  }



  private static int helper(String data, int k, int[] memo) {

    if (k == 0)

      return 1;

    int s = data.length() - k;

    if (data.charAt(s) == '0')

      return 0;

    if (memo[k] != 0) {

      return memo[k];

    }



    int result = helper(data, k - 1, memo);

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

      result += helper(data, k - 2, memo);

    }

    memo[k] = result;

    return result;

  }

share|improve this question

edited 12 mins ago

200_success

130k16153417

asked 26 mins ago

user5447339user5447339

163110

share|improve this question

edited 12 mins ago

200_success

130k16153417

asked 26 mins ago

user5447339user5447339

163110

edited 12 mins ago

200_success

130k16153417

edited 12 mins ago

200_success

130k16153417

asked 26 mins ago

user5447339user5447339

163110

asked 26 mins ago

user5447339user5447339

163110