Python程式：計算使用語法規則可以生成的字串數量

Python 伺服器端程式設計程式設計

假設我們有一個數字n，我們需要找到可以使用以下規則生成的長度為n的字串數量：

每個字元都是小寫母音字母 [a, e, i, o, u]
"a" 之後只能跟一個 "e"
"e" 之後只能跟 "a" 或 "i"
"i" 之後不能再跟 "i"
"o" 之後只能跟 "i" 或 "u"
"u" 之後只能跟一個 "a"

如果結果非常大，則將結果模 10^9 + 7。

因此，如果輸入是 n = 2，則輸出將為 10，因為我們可以生成以下兩個字母的字串：["ae", "ea", "ei", "ia", "ie", "io", "iu", "oi", "ou", "ua"]

為了解決這個問題，我們將遵循以下步驟：

m = 10^9 + 7
如果 n 等於 0，則
- 返回 0
定義五個變數 a、e、i、o、u，初始值都為 1
- 對於範圍為 0 到 n-1 的 _，執行：
  - a := e + i + u
  - e := a + i
  - i := e + o
  - o := i
  - u := i + o
返回 (a + e + i + o + u) mod m

讓我們來看下面的實現，以便更好地理解：

示例

線上演示

class Solution:
   def solve(self, n):
      m = (10 ** 9 + 7)
      if n == 0:
         return 0
      a = e = i = o = u = 1
      for _ in range(n-1):
         a, e, i, o, u = e+i+u, a+i, e+o, i, i+o
      return (a + e + i + o + u) % m

ob = Solution()
print(ob.solve(3))

輸入

輸出

Arnab Chakraborty

更新於：2020年10月8日

187 次瀏覽

開啟您的職業生涯

透過完成課程獲得認證

開始學習