计算给定移动数字小键盘序列中所有可能的字符串 [英] Count all possible strings from given mobile numeric keypad sequence

问题描述

如何计算由给定的数字序列（从2-9）形成的所有可能的字符串，其中每个数字代表一个移动按钮，并映射到3/4字母。例如：-通过按两次按钮2两次 222将其映射到A，B，C，可能形成的字符串为{ AAA， AB， BA， C}。
input = 2233，可能的字符串= { AADD， AAE， BDD， BE}。

How to count all possible string that can be formed from a given sequence of digits(from 2-9) where each digit represents 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 need a pseudo-code to implement the above problem.

推荐答案

算法/直觉：

• 如上图所示，对于单个数字，存在3-4种可能性。


• 如果我们将同一数字按2或3或4次，则显示的字符将不同。


• 就像，如果我们按 2
  
  
  
  
  • 1次- a
  
  
  • 2次- b
  
  
  • 3次次- c
  
  
  • 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

    代码：

    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));
            }
        }
    }
    

    输出：

    222 : 4
    2233 : 4
    23456789 : 1
    54667877 : 8
    5466 : 2
    7777 : 8
    22 : 2
    7898989899 : 26
    77779999 : 64
    

    这篇关于计算给定移动数字小键盘序列中所有可能的字符串的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！