algorithm - 计算键盘序列可能单词的有效算法，无需 T9

Question

免责声明:由于有一些相似但不相同的问题，请仔细阅读，我只能找到键盘与T9的引用，但没有人没有。

• 给定一个带有字母的电话键盘

2 - a,b,c

3 - d,e,f

...等等

• 给定一个数字序列，例如 222

请求:找出WITHOUT T9

可以写出多少个可能的单词

例子:

222 可以是:

array (size=4)
  0 => string 'C' (length=1)
  1 => string 'AB' (length=2)
  2 => string 'BA' (length=2)
  3 => string 'AAA' (length=3)

所以，4 种可能的解决方案

2222 可以是:

array (size=7)
  0 => string 'AC' (length=2)
  1 => string 'BB' (length=2)
  2 => string 'CA' (length=2)
  3 => string 'AAB' (length=3)
  4 => string 'ABA' (length=3)
  5 => string 'BAA' (length=3)
  6 => string 'AAAA' (length=4)

所以，7 种可能的解决方案

要求:
- 没有回溯/暴力方法
- 必须高效处理长序列(超过 1000 位数字，执行时间少于 10 秒)
- 不需要返回所有可能的词，只返回它们的个数

请注意:我不是在寻找最终算法，而是在寻找可能的方法

谢谢

Answer 1

算法/直觉:

• 如上图所示，对于一个数字，有 3-4 种可能性。
• 如果我们按同一个数字 2 次、3 次或 4 次，我们会在显示屏上看到不同的字符。
• 比如，如果我们按 2
  • 1 次 - a
  • 2 次 - b
  • 3 次 - c
• 因此，当我们计算/计算可能子串的数量时，我们需要将 subproblem(i-2),subproblem(i-3),subproblem(i-4) 值添加到我们的如果发生 i = i-1 = i-2 的总计数。
• 例如，我们以222为例。我们将采用自上而下的方法。
• 222 中的第一个2 只有一种可能性(即输入a)。
• 对于 222 中的第二个 2，它可以给我们 a 或者 2 是按 2 次给我们一个 b。因此，组合可以是 aa 和 b。
• 对于 222 中的第三个 2，它可以是 a 或 b(如果从第二个 2) 或 c。
• 因此，不。每个索引的组合 i 是 no 的总和。从 i 到 i-3 或 i-4 的匹配项，具体取决于编号。每个数字在键盘中代表的字符数。
• 请注意，如果第 i^th 个字符与 i-1 匹配，那么我们添加 dp[i-2] 而不是 dp[i-1] 因为 i-1 到 i 表示单个字符(多次按下时)。

代码:

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