Given the mapping a = 1, b = 2, … z = 26, and an encoded message, count the number of ways it can be...
$begingroup$
Given the mapping a = 1, b = 2, ... z = 26, and an encoded message,
count the number of ways it can be decoded.
For example, the message '111' would give 3, since it could be decoded
as 'aaa', 'ka', and 'ak'.
You can assume that the messages are decodable. For example, '001' is
not allowed.
class DailyCodingProblem7 {
public static void main(String args) {
String message = "11111111";
int n=message.length();
Integer ways=new Integer[n+1];
int res = solution(message,n,ways);
System.out.println(res);
}
private static int solution(String message,int k,Integer ways) {
int n=message.length();
if(k==0)
{
return 1;
}
if((int)message.charAt(n-k)==0)
{
return 0;
}
if(ways[k]!=null)
{
System.out.println(k+" : " +ways[k]);
return ways[k];
}
ways[k]=solution(message,k-1,ways);
if(k>=2 && Integer.valueOf(message.substring(n-k,n-k+2))<26)
ways[k]+=solution(message,k-2,ways);
return ways[k];
}
}
If you observe the flow, we can notice ways[k] only needs the most recent 2 values this ways[k-1] and ways[k-2]. Should I use a Hashmap or there is a better approach?
1 : 1
2 : 2
3 : 3
4 : 5
5 : 8
6 : 13
34
java algorithm programming-challenge
edited 6 hours ago
Sᴀᴍ Onᴇᴌᴀ
9,63362164
asked 12 hours ago
Maclean PintoMaclean Pinto
2165
$endgroup$
add a comment |
$begingroup$
Given the mapping a = 1, b = 2, ... z = 26, and an encoded message,
count the number of ways it can be decoded.
For example, the message '111' would give 3, since it could be decoded
as 'aaa', 'ka', and 'ak'.
You can assume that the messages are decodable. For example, '001' is
not allowed.
class DailyCodingProblem7 {
public static void main(String args) {
String message = "11111111";
int n=message.length();
Integer ways=new Integer[n+1];
int res = solution(message,n,ways);
System.out.println(res);
}
private static int solution(String message,int k,Integer ways) {
int n=message.length();
if(k==0)
{
return 1;
}
if((int)message.charAt(n-k)==0)
{
return 0;
}
if(ways[k]!=null)
{
System.out.println(k+" : " +ways[k]);
return ways[k];
}
ways[k]=solution(message,k-1,ways);
if(k>=2 && Integer.valueOf(message.substring(n-k,n-k+2))<26)
ways[k]+=solution(message,k-2,ways);
return ways[k];
}
}
If you observe the flow, we can notice ways[k] only needs the most recent 2 values this ways[k-1] and ways[k-2]. Should I use a Hashmap or there is a better approach?
1 : 1
2 : 2
3 : 3
4 : 5
5 : 8
6 : 13
34
java algorithm programming-challenge
edited 6 hours ago
Sᴀᴍ Onᴇᴌᴀ
9,63362164
asked 12 hours ago
Maclean PintoMaclean Pinto
2165
$endgroup$
add a comment |
$begingroup$
Given the mapping a = 1, b = 2, ... z = 26, and an encoded message,
count the number of ways it can be decoded.
For example, the message '111' would give 3, since it could be decoded
as 'aaa', 'ka', and 'ak'.
You can assume that the messages are decodable. For example, '001' is
not allowed.
class DailyCodingProblem7 {
public static void main(String args) {
String message = "11111111";
int n=message.length();
Integer ways=new Integer[n+1];
int res = solution(message,n,ways);
System.out.println(res);
}
private static int solution(String message,int k,Integer ways) {
int n=message.length();
if(k==0)
{
return 1;
}
if((int)message.charAt(n-k)==0)
{
return 0;
}
if(ways[k]!=null)
{
System.out.println(k+" : " +ways[k]);
return ways[k];
}
ways[k]=solution(message,k-1,ways);
if(k>=2 && Integer.valueOf(message.substring(n-k,n-k+2))<26)
ways[k]+=solution(message,k-2,ways);
return ways[k];
}
}
If you observe the flow, we can notice ways[k] only needs the most recent 2 values this ways[k-1] and ways[k-2]. Should I use a Hashmap or there is a better approach?
1 : 1
2 : 2
3 : 3
4 : 5
5 : 8
6 : 13
34
java algorithm programming-challenge
edited 6 hours ago
Sᴀᴍ Onᴇᴌᴀ
9,63362164
asked 12 hours ago
Maclean PintoMaclean Pinto
2165
$endgroup$
Given the mapping a = 1, b = 2, ... z = 26, and an encoded message,
count the number of ways it can be decoded.
For example, the message '111' would give 3, since it could be decoded
as 'aaa', 'ka', and 'ak'.
You can assume that the messages are decodable. For example, '001' is
not allowed.
class DailyCodingProblem7 {
public static void main(String args) {
String message = "11111111";
int n=message.length();
Integer ways=new Integer[n+1];
int res = solution(message,n,ways);
System.out.println(res);
}
private static int solution(String message,int k,Integer ways) {
int n=message.length();
if(k==0)
{
return 1;
}
if((int)message.charAt(n-k)==0)
{
return 0;
}
if(ways[k]!=null)
{
System.out.println(k+" : " +ways[k]);
return ways[k];
}
ways[k]=solution(message,k-1,ways);
if(k>=2 && Integer.valueOf(message.substring(n-k,n-k+2))<26)
ways[k]+=solution(message,k-2,ways);
return ways[k];
}
}
If you observe the flow, we can notice ways[k] only needs the most recent 2 values this ways[k-1] and ways[k-2]. Should I use a Hashmap or there is a better approach?
1 : 1
2 : 2
3 : 3
4 : 5
5 : 8
6 : 13
34
java algorithm programming-challenge
java algorithm programming-challenge
edited 6 hours ago
Sᴀᴍ Onᴇᴌᴀ
9,63362164
asked 12 hours ago
Maclean PintoMaclean Pinto
2165
edited 6 hours ago
Sᴀᴍ Onᴇᴌᴀ
9,63362164
asked 12 hours ago
Maclean PintoMaclean Pinto
2165
edited 6 hours ago
Sᴀᴍ Onᴇᴌᴀ
9,63362164
edited 6 hours ago
Sᴀᴍ Onᴇᴌᴀ
9,63362164
edited 6 hours ago
Sᴀᴍ Onᴇᴌᴀ
9,63362164
9,63362164
asked 12 hours ago
Maclean PintoMaclean Pinto
2165
asked 12 hours ago
Maclean PintoMaclean Pinto
2165
asked 12 hours ago
Maclean PintoMaclean Pinto
2165
2165
add a comment |
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
Houston, you have some bugs
The algorithm counts incorrectly in some cases involving zeros.
For example, there's only one way to make "10" or "20", not 2.
A different problem is the overly strict condition <26,
which excludes "26" even it can be decoded to z.
Beware of string slicing
String.substring creates a new string.
This could become expensive when repeated often.
If you change the logic to work with a char instead of a String,
then you can check if the first digit is '1',
or the first digit is '2' and the second digit is <= '6'.
Unnecessary code
This condition will never be true:
if((int)message.charAt(n-k)==0)
The characters in the input are in the range of '0'..'9',
therefore their int values are in the range of 48..57.
Unnecessary Integer
You could safely replace Integer with int,
and use a condition on zero value instead of null value.
answered 7 hours ago
janosjanos
97.8k12125350
$endgroup$
add a comment |
$begingroup$
You have almost understood the divide and conquer principle of recursion. Your solution is a bit too complex still.
- For each mapping that matches the start of the sequence...
- ...see how many times the rest of the sequence can be decoded.
- If step 2 returned a number greater than 0, add the value to the sum.
- Return sum.
The only thing you need to pass as parameters in the recursion is the sequence to be decoded and the index from which you start decoding.
As to code style, please read https://www.oracle.com/technetwork/java/codeconvtoc-136057.html
Ps. String.startsWith(prefix, offset) could be your friend right now.
answered 10 hours ago
TorbenPutkonenTorbenPutkonen
20116
$endgroup$
$begingroup$
Note that you do not need a test to add the value to the sum if the value is zero. It's not that expensive that a condition would offset the resulting amount of time used for the add.
$endgroup$
– Alexis Wilke
6 hours ago
add a comment |
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%2f213972%2fgiven-the-mapping-a-1-b-2-z-26-and-an-encoded-message-count-the-nu%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Houston, you have some bugs
The algorithm counts incorrectly in some cases involving zeros.
For example, there's only one way to make "10" or "20", not 2.
A different problem is the overly strict condition <26,
which excludes "26" even it can be decoded to z.
Beware of string slicing
String.substring creates a new string.
This could become expensive when repeated often.
If you change the logic to work with a char instead of a String,
then you can check if the first digit is '1',
or the first digit is '2' and the second digit is <= '6'.
Unnecessary code
This condition will never be true:
if((int)message.charAt(n-k)==0)
The characters in the input are in the range of '0'..'9',
therefore their int values are in the range of 48..57.
Unnecessary Integer
You could safely replace Integer with int,
and use a condition on zero value instead of null value.
answered 7 hours ago
janosjanos
97.8k12125350
$endgroup$
add a comment |
$begingroup$
Houston, you have some bugs
The algorithm counts incorrectly in some cases involving zeros.
For example, there's only one way to make "10" or "20", not 2.
A different problem is the overly strict condition <26,
which excludes "26" even it can be decoded to z.
Beware of string slicing
String.substring creates a new string.
This could become expensive when repeated often.
If you change the logic to work with a char instead of a String,
then you can check if the first digit is '1',
or the first digit is '2' and the second digit is <= '6'.
Unnecessary code
This condition will never be true:
if((int)message.charAt(n-k)==0)
The characters in the input are in the range of '0'..'9',
therefore their int values are in the range of 48..57.
Unnecessary Integer
You could safely replace Integer with int,
and use a condition on zero value instead of null value.
answered 7 hours ago
janosjanos
97.8k12125350
$endgroup$
add a comment |
$begingroup$
Houston, you have some bugs
The algorithm counts incorrectly in some cases involving zeros.
For example, there's only one way to make "10" or "20", not 2.
A different problem is the overly strict condition <26,
which excludes "26" even it can be decoded to z.
Beware of string slicing
String.substring creates a new string.
This could become expensive when repeated often.
If you change the logic to work with a char instead of a String,
then you can check if the first digit is '1',
or the first digit is '2' and the second digit is <= '6'.
Unnecessary code
This condition will never be true:
if((int)message.charAt(n-k)==0)
The characters in the input are in the range of '0'..'9',
therefore their int values are in the range of 48..57.
Unnecessary Integer
You could safely replace Integer with int,
and use a condition on zero value instead of null value.
answered 7 hours ago
janosjanos
97.8k12125350
$endgroup$
Houston, you have some bugs
The algorithm counts incorrectly in some cases involving zeros.
For example, there's only one way to make "10" or "20", not 2.
A different problem is the overly strict condition <26,
which excludes "26" even it can be decoded to z.
Beware of string slicing
String.substring creates a new string.
This could become expensive when repeated often.
If you change the logic to work with a char instead of a String,
then you can check if the first digit is '1',
or the first digit is '2' and the second digit is <= '6'.
Unnecessary code
This condition will never be true:
if((int)message.charAt(n-k)==0)
The characters in the input are in the range of '0'..'9',
therefore their int values are in the range of 48..57.
Unnecessary Integer
You could safely replace Integer with int,
and use a condition on zero value instead of null value.
answered 7 hours ago
janosjanos
97.8k12125350
answered 7 hours ago
janosjanos
97.8k12125350
answered 7 hours ago
janosjanos
97.8k12125350
answered 7 hours ago
janosjanos
97.8k12125350
97.8k12125350
add a comment |
add a comment |
$begingroup$
You have almost understood the divide and conquer principle of recursion. Your solution is a bit too complex still.
- For each mapping that matches the start of the sequence...
- ...see how many times the rest of the sequence can be decoded.
- If step 2 returned a number greater than 0, add the value to the sum.
- Return sum.
The only thing you need to pass as parameters in the recursion is the sequence to be decoded and the index from which you start decoding.
As to code style, please read https://www.oracle.com/technetwork/java/codeconvtoc-136057.html
Ps. String.startsWith(prefix, offset) could be your friend right now.
answered 10 hours ago
TorbenPutkonenTorbenPutkonen
20116
$endgroup$
$begingroup$
Note that you do not need a test to add the value to the sum if the value is zero. It's not that expensive that a condition would offset the resulting amount of time used for the add.
$endgroup$
– Alexis Wilke
6 hours ago
add a comment |
$begingroup$
You have almost understood the divide and conquer principle of recursion. Your solution is a bit too complex still.
- For each mapping that matches the start of the sequence...
- ...see how many times the rest of the sequence can be decoded.
- If step 2 returned a number greater than 0, add the value to the sum.
- Return sum.
The only thing you need to pass as parameters in the recursion is the sequence to be decoded and the index from which you start decoding.
As to code style, please read https://www.oracle.com/technetwork/java/codeconvtoc-136057.html
Ps. String.startsWith(prefix, offset) could be your friend right now.
answered 10 hours ago
TorbenPutkonenTorbenPutkonen
20116
$endgroup$
$begingroup$
Note that you do not need a test to add the value to the sum if the value is zero. It's not that expensive that a condition would offset the resulting amount of time used for the add.
$endgroup$
– Alexis Wilke
6 hours ago
add a comment |
$begingroup$
You have almost understood the divide and conquer principle of recursion. Your solution is a bit too complex still.
- For each mapping that matches the start of the sequence...
- ...see how many times the rest of the sequence can be decoded.
- If step 2 returned a number greater than 0, add the value to the sum.
- Return sum.
The only thing you need to pass as parameters in the recursion is the sequence to be decoded and the index from which you start decoding.
As to code style, please read https://www.oracle.com/technetwork/java/codeconvtoc-136057.html
Ps. String.startsWith(prefix, offset) could be your friend right now.
answered 10 hours ago
TorbenPutkonenTorbenPutkonen
20116
$endgroup$
You have almost understood the divide and conquer principle of recursion. Your solution is a bit too complex still.
- For each mapping that matches the start of the sequence...
- ...see how many times the rest of the sequence can be decoded.
- If step 2 returned a number greater than 0, add the value to the sum.
- Return sum.
The only thing you need to pass as parameters in the recursion is the sequence to be decoded and the index from which you start decoding.
As to code style, please read https://www.oracle.com/technetwork/java/codeconvtoc-136057.html
Ps. String.startsWith(prefix, offset) could be your friend right now.
answered 10 hours ago
TorbenPutkonenTorbenPutkonen
20116
edited 10 hours ago
answered 10 hours ago
TorbenPutkonenTorbenPutkonen
20116
answered 10 hours ago
TorbenPutkonenTorbenPutkonen
20116
answered 10 hours ago
TorbenPutkonenTorbenPutkonen
20116
20116
$begingroup$
Note that you do not need a test to add the value to the sum if the value is zero. It's not that expensive that a condition would offset the resulting amount of time used for the add.
$endgroup$
– Alexis Wilke
6 hours ago
add a comment |
$begingroup$
Note that you do not need a test to add the value to the sum if the value is zero. It's not that expensive that a condition would offset the resulting amount of time used for the add.
$endgroup$
– Alexis Wilke
6 hours ago
$begingroup$
Note that you do not need a test to add the value to the sum if the value is zero. It's not that expensive that a condition would offset the resulting amount of time used for the add.
$endgroup$
– Alexis Wilke
6 hours ago
$begingroup$
Note that you do not need a test to add the value to the sum if the value is zero. It's not that expensive that a condition would offset the resulting amount of time used for the add.
$endgroup$
– Alexis Wilke
6 hours ago
add a comment |
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%2f213972%2fgiven-the-mapping-a-1-b-2-z-26-and-an-encoded-message-count-the-nu%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
