java - 字母表可以组成多少个 N 长的字符串？需要一个高效的算法

Question

问题是从字母表中可以组成多少个长度为 N 的字符串。

条件是:

1. 字符串中的字母可以重复
2. 只有在字母表中与字母相邻的字母才能在字符串中并排放置。例如，如果 N = 4，则字符串可以是 ABCD、ABAB、ABCB、WXYZ、XWXW 等。它们不能是 ABCE、CDEG、AAAA，因为只有字母表中相邻的字母才能并排放置。

当我有 N 的答案时:

• 如果 N = 3，答案是 98
• 如果 N = 4，答案是 192
• 如果 N = 8，答案是 2896
• 如果 N = 15，答案是 342840
• 如果 N = 30，则答案为 9841989098
• 如果 N = 40，答案是 9329564680878

我需要在 N = 50 时找到答案。我所做的算法在 10 秒内正确获取答案直到 30。然而，在 30 之后，我认为由于我的算法的递归性质，它一直在运行，我还没有得到答案。

这是我的java代码:

class Alphabet {

  public int n;

  public long counter = 0;

  public static void main(String[] args) {
    Alphabet a = new Alphabet(15);
    a.run();
  }

  public Alphabet(int n) {
    this.n = n;
  }

  public void run() {

    for (int i = 0; i < 13; i++) {
        this.attach(i, 1);
    }

    System.out.println(this.counter * 2);
  }

  public boolean attach(int letter, int length) {

    if (length == this.n) {
        this.counter++;
        return true;
    }

    if (letter == 0) {
        this.attach(1, length + 1);
        return true;
    }

    if (letter == 25) {
        this.attach(24, length + 1);
        return true;
    }

    this.attach(letter - 1, length + 1);
    this.attach(letter + 1, length + 1);

    return true;
  }
}

是否有更有效的方法来获取答案？

Answer 1

对于每个字母，计算以该字母结尾的长度为 1 的字符串的数量。对于所有字母，这是 1。

如果您知道以每个字母结尾的 n 个字母字符串的数量，那么很容易计算以每个字母结尾的 n+1 个字母字符串的数量。根据您的规则，这需要 O(alphabet_size) 时间。重复此操作，直到达到 n=N。然后只需将所有字母的计数相加即可。