number of ways to decode a string?Google Code jam puzzle - Welcome to Code JamMystery sum with placeholder...
What is a term for a function that when called repeatedly, has the same effect as calling once?
Must 40/100G uplink ports on a 10G switch be connected to another switch?
When was drinking water recognized as crucial in marathon running?
When to use mean vs median
Can I solder 12/2 Romex to extend wire 5 ft?
Wardrobe above a wall with fuse boxes
PTIJ: Aharon, King of Egypt
Is there a math equivalent to the conditional ternary operator?
Rationale to prefer local variables over instance variables?
How to get the first element while continue streaming?
Meaning of word ягоза
Relationship between the symmetry number of a molecule as used in rotational spectroscopy and point group
I encountered my boss during an on-site interview at another company. Should I bring it up when seeing him next time?
Practical reasons to have both a large police force and bounty hunting network?
Where is the fallacy here?
Quitting employee has privileged access to critical information
Can the Shape Water Cantrip be used to manipulate blood?
Is there a full canon version of Tyrion's jackass/honeycomb joke?
Is there a way to find out the age of climbing ropes?
Did Amazon pay $0 in taxes last year?
Is there a limit on the maximum number of future jobs queued in an org?
Can an earth elemental drown/bury its opponent underground using earth glide?
Reason why dimensional travelling would be restricted
Draw bounding region by list of points
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
$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
asked 6 mins ago
user5447339user5447339
158110
$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
asked 6 mins ago
user5447339user5447339
158110
$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
asked 6 mins ago
user5447339user5447339
158110
$endgroup$
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
java algorithm
asked 6 mins ago
user5447339user5447339
158110
asked 6 mins ago
user5447339user5447339
158110
asked 6 mins ago
user5447339user5447339
158110
asked 6 mins ago
user5447339user5447339
158110
asked 6 mins ago
user5447339user5447339
158110
158110
add a comment |
add a comment |
0
active
oldest
votes
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["\$", "\$"]]);
});
});
}, "mathjax-editing");
StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "196"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f214878%2fnumber-of-ways-to-decode-a-string%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
0
active
oldest
votes
0
active
oldest
votes
active
oldest
votes
active
oldest
votes
Thanks for contributing an answer to Code Review Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f214878%2fnumber-of-ways-to-decode-a-string%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
