Mixing
count all possible strings from given mobile numeric keypad sequence
up vote
-1
down vote
favorite
I want to know the concept how to count all possible string that can be formed from a given sequence of digits(from 2-9) where each digit represent a mobile button and is mapped to 3/4 alphabet. eg:- 2 is mapped to A,B,C, by pressing the button 2 three times "222", possible strings that can be formed are {"AAA","AB","BA","C"}.
input= "2233", possible strings={"AADD","AAE","BDD","BE"}
I want a pseudo code to implement the above problem.
algorithm dynamic-programming
asked 2 days ago
Prachi Katlam
14
add a comment |
up vote
-1
down vote
favorite
I want to know the concept how to count all possible string that can be formed from a given sequence of digits(from 2-9) where each digit represent a mobile button and is mapped to 3/4 alphabet. eg:- 2 is mapped to A,B,C, by pressing the button 2 three times "222", possible strings that can be formed are {"AAA","AB","BA","C"}.
input= "2233", possible strings={"AADD","AAE","BDD","BE"}
I want a pseudo code to implement the above problem.
algorithm dynamic-programming
asked 2 days ago
Prachi Katlam
14
What have YOU tried so far? Show us YOUR code. There did you get stuck?
– MrSmith42
2 days ago
i don't have a code, i need an idea to how to do it. probably it can be solved by a recursive solution by counting the contiguous occurrence of the digit and looking for possible stings that can be formed, but it will take too much time. looking for a dp solution
– Prachi Katlam
2 days ago
add a comment |
up vote
-1
down vote
favorite
up vote
-1
down vote
favorite
I want to know the concept how to count all possible string that can be formed from a given sequence of digits(from 2-9) where each digit represent a mobile button and is mapped to 3/4 alphabet. eg:- 2 is mapped to A,B,C, by pressing the button 2 three times "222", possible strings that can be formed are {"AAA","AB","BA","C"}.
input= "2233", possible strings={"AADD","AAE","BDD","BE"}
I want a pseudo code to implement the above problem.
algorithm dynamic-programming
asked 2 days ago
Prachi Katlam
14
I want to know the concept how to count all possible string that can be formed from a given sequence of digits(from 2-9) where each digit represent a mobile button and is mapped to 3/4 alphabet. eg:- 2 is mapped to A,B,C, by pressing the button 2 three times "222", possible strings that can be formed are {"AAA","AB","BA","C"}.
input= "2233", possible strings={"AADD","AAE","BDD","BE"}
I want a pseudo code to implement the above problem.
algorithm dynamic-programming
algorithm dynamic-programming
asked 2 days ago
Prachi Katlam
14
asked 2 days ago
Prachi Katlam
14
asked 2 days ago
Prachi Katlam
14
asked 2 days ago
Prachi Katlam
14
asked 2 days ago
Prachi Katlam
14
14
What have YOU tried so far? Show us YOUR code. There did you get stuck?
– MrSmith42
2 days ago
i don't have a code, i need an idea to how to do it. probably it can be solved by a recursive solution by counting the contiguous occurrence of the digit and looking for possible stings that can be formed, but it will take too much time. looking for a dp solution
– Prachi Katlam
2 days ago
add a comment |
What have YOU tried so far? Show us YOUR code. There did you get stuck?
– MrSmith42
2 days ago
i don't have a code, i need an idea to how to do it. probably it can be solved by a recursive solution by counting the contiguous occurrence of the digit and looking for possible stings that can be formed, but it will take too much time. looking for a dp solution
– Prachi Katlam
2 days ago
What have YOU tried so far? Show us YOUR code. There did you get stuck?
– MrSmith42
2 days ago
What have YOU tried so far? Show us YOUR code. There did you get stuck?
– MrSmith42
2 days ago
i don't have a code, i need an idea to how to do it. probably it can be solved by a recursive solution by counting the contiguous occurrence of the digit and looking for possible stings that can be formed, but it will take too much time. looking for a dp solution
– Prachi Katlam
2 days ago
i don't have a code, i need an idea to how to do it. probably it can be solved by a recursive solution by counting the contiguous occurrence of the digit and looking for possible stings that can be formed, but it will take too much time. looking for a dp solution
– Prachi Katlam
2 days ago
add a comment |
1 Answer
1
active
oldest
votes
up vote
0
down vote
Algorithm/Intuition:
- As it represents in the above image, for a single digit, there are 3-4 possibilities.
- If we press the same digit 2 or 3 or 4 times, we get different characters on the display.
- Like, if we press
2
- 1 time -
a
- 2 times -
b
- 3 times -
c
- 1 time -
- So, when we calculate/count the number of possible substrings, we need to add
subproblem(i-2),subproblem(i-3),subproblem(i-4)values to our total count if it happens thati = i-1 = i-2. - For example, let's take 222. We will adopt a top-bottom approach.
- First 2 in 222 has only 1 possibility(which will be typing
a). - For second 2 in 222, it can give us either
aor it might be that2was pressed 2 times giving us ab. So, combinations can beaaandb. - For third 2 in 222, it can be
aorb(if started from second2) orc. - Hence, no. of combinations for each index
iis sum of no. of matches fromitilli-3ori-4, depending upon no. of characters each digit represents in the keypad. - Note that if ith character matches with
i-1, then we adddp[i-2]and notdp[i-1]sincei-1 till irepresents a single character (when pressed multiple times).
Code:
import static java.lang.System.out;
public class Solution{
public static int possibleStringCount(String s){
int len = s.length();
int dp = new int[len];
dp[0] = 1;// possibility is 1 for a single character
for(int i=1;i<len;++i){
int possible_chars_length = numberOfRepresentedCharacters(s.charAt(i)-'0') - 1;// because current character itself counts as 1.
dp[i] = 0;
for(int j=i;j>=0;j--){
if(i - possible_chars_length > j) break;
if(s.charAt(i) == s.charAt(j)){
if(j-1 > -1){
dp[i] += dp[j-1];
}else{
dp[i] += 1;// if there are no combinations before it, then it represents a single character
}
}
}
}
return dp[len-1];
}
private static int numberOfRepresentedCharacters(int digit){
if(digit == 7 || digit == 9) return 4;
return 3;// it is assumed that digits are between 2-9 always
}
public static void main(String args) {
String tests = {
"222","2233","23456789","54667877","5466","7777","22","7898989899","77779999"
};
for(String testcase : tests){
out.println(testcase + " : " + possibleStringCount(testcase));
}
}
}
Output:
222 : 4
2233 : 4
23456789 : 1
54667877 : 8
5466 : 2
7777 : 8
22 : 2
7898989899 : 26
77779999 : 64
answered 2 days ago
vivek_23
1,8661517
add a comment |
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
0
down vote
Algorithm/Intuition:
- As it represents in the above image, for a single digit, there are 3-4 possibilities.
- If we press the same digit 2 or 3 or 4 times, we get different characters on the display.
- Like, if we press
2
- 1 time -
a
- 2 times -
b
- 3 times -
c
- 1 time -
- So, when we calculate/count the number of possible substrings, we need to add
subproblem(i-2),subproblem(i-3),subproblem(i-4)values to our total count if it happens thati = i-1 = i-2. - For example, let's take 222. We will adopt a top-bottom approach.
- First 2 in 222 has only 1 possibility(which will be typing
a). - For second 2 in 222, it can give us either
aor it might be that2was pressed 2 times giving us ab. So, combinations can beaaandb. - For third 2 in 222, it can be
aorb(if started from second2) orc. - Hence, no. of combinations for each index
iis sum of no. of matches fromitilli-3ori-4, depending upon no. of characters each digit represents in the keypad. - Note that if ith character matches with
i-1, then we adddp[i-2]and notdp[i-1]sincei-1 till irepresents a single character (when pressed multiple times).
Code:
import static java.lang.System.out;
public class Solution{
public static int possibleStringCount(String s){
int len = s.length();
int dp = new int[len];
dp[0] = 1;// possibility is 1 for a single character
for(int i=1;i<len;++i){
int possible_chars_length = numberOfRepresentedCharacters(s.charAt(i)-'0') - 1;// because current character itself counts as 1.
dp[i] = 0;
for(int j=i;j>=0;j--){
if(i - possible_chars_length > j) break;
if(s.charAt(i) == s.charAt(j)){
if(j-1 > -1){
dp[i] += dp[j-1];
}else{
dp[i] += 1;// if there are no combinations before it, then it represents a single character
}
}
}
}
return dp[len-1];
}
private static int numberOfRepresentedCharacters(int digit){
if(digit == 7 || digit == 9) return 4;
return 3;// it is assumed that digits are between 2-9 always
}
public static void main(String args) {
String tests = {
"222","2233","23456789","54667877","5466","7777","22","7898989899","77779999"
};
for(String testcase : tests){
out.println(testcase + " : " + possibleStringCount(testcase));
}
}
}
Output:
222 : 4
2233 : 4
23456789 : 1
54667877 : 8
5466 : 2
7777 : 8
22 : 2
7898989899 : 26
77779999 : 64
answered 2 days ago
vivek_23
1,8661517
add a comment |
up vote
0
down vote
Algorithm/Intuition:
- As it represents in the above image, for a single digit, there are 3-4 possibilities.
- If we press the same digit 2 or 3 or 4 times, we get different characters on the display.
- Like, if we press
2
- 1 time -
a
- 2 times -
b
- 3 times -
c
- 1 time -
- So, when we calculate/count the number of possible substrings, we need to add
subproblem(i-2),subproblem(i-3),subproblem(i-4)values to our total count if it happens thati = i-1 = i-2. - For example, let's take 222. We will adopt a top-bottom approach.
- First 2 in 222 has only 1 possibility(which will be typing
a). - For second 2 in 222, it can give us either
aor it might be that2was pressed 2 times giving us ab. So, combinations can beaaandb. - For third 2 in 222, it can be
aorb(if started from second2) orc. - Hence, no. of combinations for each index
iis sum of no. of matches fromitilli-3ori-4, depending upon no. of characters each digit represents in the keypad. - Note that if ith character matches with
i-1, then we adddp[i-2]and notdp[i-1]sincei-1 till irepresents a single character (when pressed multiple times).
Code:
import static java.lang.System.out;
public class Solution{
public static int possibleStringCount(String s){
int len = s.length();
int dp = new int[len];
dp[0] = 1;// possibility is 1 for a single character
for(int i=1;i<len;++i){
int possible_chars_length = numberOfRepresentedCharacters(s.charAt(i)-'0') - 1;// because current character itself counts as 1.
dp[i] = 0;
for(int j=i;j>=0;j--){
if(i - possible_chars_length > j) break;
if(s.charAt(i) == s.charAt(j)){
if(j-1 > -1){
dp[i] += dp[j-1];
}else{
dp[i] += 1;// if there are no combinations before it, then it represents a single character
}
}
}
}
return dp[len-1];
}
private static int numberOfRepresentedCharacters(int digit){
if(digit == 7 || digit == 9) return 4;
return 3;// it is assumed that digits are between 2-9 always
}
public static void main(String args) {
String tests = {
"222","2233","23456789","54667877","5466","7777","22","7898989899","77779999"
};
for(String testcase : tests){
out.println(testcase + " : " + possibleStringCount(testcase));
}
}
}
Output:
222 : 4
2233 : 4
23456789 : 1
54667877 : 8
5466 : 2
7777 : 8
22 : 2
7898989899 : 26
77779999 : 64
answered 2 days ago
vivek_23
1,8661517
add a comment |
up vote
0
down vote
up vote
0
down vote
Algorithm/Intuition:
- As it represents in the above image, for a single digit, there are 3-4 possibilities.
- If we press the same digit 2 or 3 or 4 times, we get different characters on the display.
- Like, if we press
2
- 1 time -
a
- 2 times -
b
- 3 times -
c
- 1 time -
- So, when we calculate/count the number of possible substrings, we need to add
subproblem(i-2),subproblem(i-3),subproblem(i-4)values to our total count if it happens thati = i-1 = i-2. - For example, let's take 222. We will adopt a top-bottom approach.
- First 2 in 222 has only 1 possibility(which will be typing
a). - For second 2 in 222, it can give us either
aor it might be that2was pressed 2 times giving us ab. So, combinations can beaaandb. - For third 2 in 222, it can be
aorb(if started from second2) orc. - Hence, no. of combinations for each index
iis sum of no. of matches fromitilli-3ori-4, depending upon no. of characters each digit represents in the keypad. - Note that if ith character matches with
i-1, then we adddp[i-2]and notdp[i-1]sincei-1 till irepresents a single character (when pressed multiple times).
Code:
import static java.lang.System.out;
public class Solution{
public static int possibleStringCount(String s){
int len = s.length();
int dp = new int[len];
dp[0] = 1;// possibility is 1 for a single character
for(int i=1;i<len;++i){
int possible_chars_length = numberOfRepresentedCharacters(s.charAt(i)-'0') - 1;// because current character itself counts as 1.
dp[i] = 0;
for(int j=i;j>=0;j--){
if(i - possible_chars_length > j) break;
if(s.charAt(i) == s.charAt(j)){
if(j-1 > -1){
dp[i] += dp[j-1];
}else{
dp[i] += 1;// if there are no combinations before it, then it represents a single character
}
}
}
}
return dp[len-1];
}
private static int numberOfRepresentedCharacters(int digit){
if(digit == 7 || digit == 9) return 4;
return 3;// it is assumed that digits are between 2-9 always
}
public static void main(String args) {
String tests = {
"222","2233","23456789","54667877","5466","7777","22","7898989899","77779999"
};
for(String testcase : tests){
out.println(testcase + " : " + possibleStringCount(testcase));
}
}
}
Output:
222 : 4
2233 : 4
23456789 : 1
54667877 : 8
5466 : 2
7777 : 8
22 : 2
7898989899 : 26
77779999 : 64
answered 2 days ago
vivek_23
1,8661517
Algorithm/Intuition:
- As it represents in the above image, for a single digit, there are 3-4 possibilities.
- If we press the same digit 2 or 3 or 4 times, we get different characters on the display.
- Like, if we press
2
- 1 time -
a
- 2 times -
b
- 3 times -
c
- 1 time -
- So, when we calculate/count the number of possible substrings, we need to add
subproblem(i-2),subproblem(i-3),subproblem(i-4)values to our total count if it happens thati = i-1 = i-2. - For example, let's take 222. We will adopt a top-bottom approach.
- First 2 in 222 has only 1 possibility(which will be typing
a). - For second 2 in 222, it can give us either
aor it might be that2was pressed 2 times giving us ab. So, combinations can beaaandb. - For third 2 in 222, it can be
aorb(if started from second2) orc. - Hence, no. of combinations for each index
iis sum of no. of matches fromitilli-3ori-4, depending upon no. of characters each digit represents in the keypad. - Note that if ith character matches with
i-1, then we adddp[i-2]and notdp[i-1]sincei-1 till irepresents a single character (when pressed multiple times).
Code:
import static java.lang.System.out;
public class Solution{
public static int possibleStringCount(String s){
int len = s.length();
int dp = new int[len];
dp[0] = 1;// possibility is 1 for a single character
for(int i=1;i<len;++i){
int possible_chars_length = numberOfRepresentedCharacters(s.charAt(i)-'0') - 1;// because current character itself counts as 1.
dp[i] = 0;
for(int j=i;j>=0;j--){
if(i - possible_chars_length > j) break;
if(s.charAt(i) == s.charAt(j)){
if(j-1 > -1){
dp[i] += dp[j-1];
}else{
dp[i] += 1;// if there are no combinations before it, then it represents a single character
}
}
}
}
return dp[len-1];
}
private static int numberOfRepresentedCharacters(int digit){
if(digit == 7 || digit == 9) return 4;
return 3;// it is assumed that digits are between 2-9 always
}
public static void main(String args) {
String tests = {
"222","2233","23456789","54667877","5466","7777","22","7898989899","77779999"
};
for(String testcase : tests){
out.println(testcase + " : " + possibleStringCount(testcase));
}
}
}
Output:
222 : 4
2233 : 4
23456789 : 1
54667877 : 8
5466 : 2
7777 : 8
22 : 2
7898989899 : 26
77779999 : 64
answered 2 days ago
vivek_23
1,8661517
answered 2 days ago
vivek_23
1,8661517
answered 2 days ago
vivek_23
1,8661517
answered 2 days ago
vivek_23
1,8661517
1,8661517
add a comment |
add a comment |
draft saved
draft discarded
draft saved
draft discarded
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%2fstackoverflow.com%2fquestions%2f53373675%2fcount-all-possible-strings-from-given-mobile-numeric-keypad-sequence%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
What have YOU tried so far? Show us YOUR code. There did you get stuck?
– MrSmith42
2 days ago
i don't have a code, i need an idea to how to do it. probably it can be solved by a recursive solution by counting the contiguous occurrence of the digit and looking for possible stings that can be formed, but it will take too much time. looking for a dp solution
– Prachi Katlam
2 days ago