count all possible strings from given mobile numer

问题:

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.

回答1:

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
• 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 that i = 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 a or it might be that 2 was pressed 2 times giving us a b. So, combinations can be aa and b.
• For third 2 in 222, it can be a or b(if started from second 2) or c.
• Hence, no. of combinations for each index i is sum of no. of matches from i till i-3 or i-4, depending upon no. of characters each digit represents in the keypad.
• Note that if i^th character matches with i-1, then we add dp[i-2] and not dp[i-1] since i-1 till i represents 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