LeetCode 解題紀錄 #1

1220. Count Vowels Permutation

└─解題難度：HARD

Kevin Cheng

Published in

Cow Say

19 min readJul 7, 2021

最近沉迷力扣無法自拔😆

本篇文章為我的解題紀錄，所以寫的不只是最終的解決方案而已。會從我的觀察和分析寫起，順著思路推導出答案。除了推理的部分，還會提及實作方式以及實作時遇見的瓶頸。

題目任意門在此，歡迎有興趣的人在看題解之前先來一起試著接受挑戰！

Count Vowels Permutation — LeetCode

Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared…

leetcode.com

題目說明

懶得看題目也沒關係，我直接在這簡單說明一下。

測資會給我們一個整數 n 滿足 1 ≤ n ≤ 20000，我們需要找出符合下列規則且長度恰好為 n 的所有字串。

字母只能是小寫，且只包含 a、e、i、o、u 五個字母。
跟隨在字母 a 後面只能是 e。
跟隨在字母 e 後面的只能是 a 或 i。
字母 i 後面不能跟隨 i。（也就是字母 i 後面可以是 a、e、o、u 任一）
跟隨在字母 o 後面的只能是 i 或 u。
跟隨在字母 u 後面的只能是 a。

另外由於答案數字超級大，須以 1⁰⁹ + 7 的模數（Modulo）表示，也就是把原始答案和 1⁰⁹ + 7 取餘數返回。

實戰成績

我總共用了兩種語言實作，分別是 JavaScript 和 Python3。

通常我的第一次提交都會是暴力解法──先追求可行，然後逐步優化追求更好的表現，但也不一定每次都能夠順利產生新的想法。值得慶幸的是至今做的每一題平均會提交2~3次 AC 的答案。

我在解題的時候都是以 JavaScript 為主，至於為什麼這題會用到 Python3 會在後續的說明中提到，就請各位拭目以待。

JavaScript

最初的幾個版本都用 JavaScript 實作，做了無數嘗試、撞了無數牆。

在最佳紀錄中，速度贏了93.1%的人，記憶體使用則贏了約54%。

“Your runtime beats 93.1% of javascript submissions.”

Python3

最後一個版本用了 Python3 實作。

偷偷說溜嘴，理由是因為 Python3 的整數基本上是沒有上限的，我想知道用 Python3 整數數值實現會不會比我在 JavaScript 的 BigInt 還快。會用「基本上」是因為還是有物理上的限制，也就是記憶體容量的限制存在。

總而言之，BigInt 你實在是讓我太失望了 (ಥ﹏ಥ)

Python3 的解法一鳴驚人，速度贏了100%的人，記憶體使用則贏了50.39%。

“Your runtime beats 100% of python3 submissions.”

解題分析

試著揣摩一下題目的思路。

動態規劃

已知當 n=1 的時候，我們有五種選擇：a、e、i、o、u。

當 n=2 時，我們可以推得以下這幾件事情：

上一層的 a 為這一層提供了一個選擇：e。
上一層的 e 為這一層提供了二個選擇：a、i。
上一層的 i 為這一層提供了四個選擇：a、e、o、u。
上一層的 o 為這一層提供了二個選擇：i、u。
上一層的 u 為這一層提供了一個選擇：a。

透過這幾件事情，我們可以總結，當 n=2 時，我們有 10 種選擇：e、a、i、a、e、o、u、i、u、a。

有人可能會好奇重覆的要不要算？你要記得這些選擇是字串中第二個字元的選擇數，即便重覆的字元他的前一個字元是不一樣的，所以要分別算成兩種組合。如上述 n=2 中，a 出現了三次是因為 “ea”、”ia”、”ua”。

由這個思路可以知道，我們的目標是循著 n 不斷遞增，找出當層可能的選擇數即為答案。若把如此的選擇分歧想作是一棵樹狀結構，我們在計算的便是葉子的數量。

這邊我的第一個實作想法是遞迴，不過大概只耽誤了我十分鐘就果斷放棄了 😂

由於放棄得太快，害我還來不及讓它進版本控制就被我刪改了。以下是事後還原得代碼片段。姑且感受一下就好，不用太講究。

乾淨簡約，完美實現了上面的推論。

但有兩個很嚴重的問題，都跟一件事情有關：1 ≤ n ≤ 20000。

儘管我順利以一個方法實現了每一層要做的事情──計算選擇組合，然後遞回呼叫它以取得最終的組合。也就是說我最多要呼叫 19999 次才能取得 n=20000 的答案……就算你能挺得住，你的 Call stack 挺得住嗎？

去跟它問聲好吧。

還有第二個問題便是第二個參數 vowels 會包含了上一層所有組合，根據題目所述答案數字超級大，也就是這個陣列的元素超級多……就算你能挺得住，你的 Heap 挺得住嗎？

也跟它問聲好吧。

在種種硬體的限制下是任性不得我們的，即便你跟它們都問好了。這題的動態規劃邏輯不難，難在我們需要更快更省的解決方案。

遞回問題相對好解，疊代這個選項呼之欲出已經在等著我們了。

容量問題要秉持著血拚時物比三家、錙銖必較的心態試著捫心自問，我們真的需要知道每個組合嗎？是不是只要一個數字（或幾個數字）就夠用了？

疊代 + 簡化資結

透過疊代和簡化資料結構的方式實現的程式碼如下。

在寫碼時我特別注意了第 10 行，用了 Array.from() 將 Object.entries() 產生的疊代器展開為一陣列，因為我在下面的迴圈中將要修改到 stats 物件的內容，因此做了一次複製。而第 13 行到第 33 行這一大坨 switch 很直觀的表現了題目那幾項規則。

這也是我第一次取得 AC 的程式碼，成績大約是 236ms，跟上面展示的 JavaScript 最佳成績相去還是有一段可觀落差，這樣的落差主要來自 switch 中的那一坨邏輯。

經擅長偷雞摸狗的友人提點，我不應該想著「上一層是 a 的時候這一層會產生 e」（見第 14、15 行），我應該要反過來想──「這一層是 a 時是因為上一層哪些字母的存在」──這一層有 a 是因為上一層有 e、i 或 u 的存在，按題目規則所示，只有 e、i 或 u 後面有可能跟隨著 a，也就是上一層 e、i 和 u 的數量決定了這一層 a 的數量。

如此一來可以減少計算量，因為在原先的做法內，for 迴圈中 a ~ u 每個字母都會進去迴圈一次，因此 switch 每個分支都一定會走過，只是有可能該層沒有該字母所以 count 為 0，但依然會進行加法計算。整個 switch 中有 10 個 += 運算子（可以當作 10 次加法 10 次賦值），改變邏輯後只剩下 5 次加法、5 次賦值。

單這一項改變讓我的成績從 236ms 進步到了 112ms，幾乎剛好折半。

然而我還做了另一項改變，就是不再使用 stats 物件存取五個數值。第一是用物件時我為了遍歷並同時修改物件內容，而使用了 Object.entries() 和 Array.from() 複製內容，並在最後返回前計算時用了 Object.values() 遍歷每個值並用 Array#reduce() 進行加總。

我改為直接宣告五個變數，並直接用賦值方式複製內容值，最後直接對五個變數進行加總。

邏輯上來說，要做的事情一樣多，但是 Object 或 Array 內部肯定除了遍歷或是加總還有一些為了維護狀態、維護 API 通用性的邏輯存在，一般狀況下我們會忽略這些判斷所造成的效能影響，但顯然在這個實現裡面，我們後續的動作都已經很輕量了，輕量到這些細微的角落都足以撼動最後的成果。

在這個修改中，我又從 112ms 進步到了 76ms。

總結來說，小而美的實現最棒了😚

修改後的程式碼如下：

以為故事到這裡就結束了嗎？那你就是太天真了！

矩陣快速冪

想更快算出費氏數列嗎？來看看矩陣快速冪吧！

先前從這篇文章認識矩陣快速冪之後，始終沒有找到合適的地方可以應用，直到讓我遇見了這個機會！建議還不知道什麼是矩陣快速冪的人，可以從連結進去專欄惡補一下。

從最後這份程式碼，我們可以觀察到 while 迴圈內一直反覆按同一個模式在運算：這一層的 a 總是把上一層 e、i 和 u 的值加總、e 總是把 a 和 i 的值加總……等等。

因此我們可以將這個模式公式化：

a' = 0*a + 1*e + 1*i + 0*o + 1*u
e' = 1*a + 0*e + 1*i + 0*o + 0*u
i' = 0*a + 1*e + 0*i + 1*o + 0*u
o' = 0*a + 0*e + 1*i + 0*o + 0*u
u' = 0*a + 0*e + 1*i + 1*o + 0*u

刻意把係數為 0 的項目也寫出來了，從這邊我們可以將這組公式寫作矩陣乘法。如果還沒忘記矩陣如何乘法的話，我們可將公式寫作：

| a' |   | 0 1 1 0 1 |   | a |
| b' |   | 1 0 1 0 0 |   | e |
| c' | = | 0 1 0 1 0 | * | i |
| d' |   | 0 0 1 0 0 |   | o |
| e' |   | 0 0 1 1 0 |   | u |

由此可知，每一次 while 迴圈我們都將一個常數的轉移矩陣 M 乘上一向量 V [[a], [e], [i], [o], [u]]。

已知當 n=1 時，向量 V 為 [[a], [e], [i], [o], [u]]，則 n=k 時，我們只須將轉移矩陣 M 的 k-1 次方乘上向量 V 就可以得到系統最後的狀態。

V(n=k) = M * V(n=k-1) = M * M * V(n=k-2) = ... = M^(k-1) * V(n=1)

如此一來我們可以運用矩陣快速冪，計算出 M^(k-1) 再乘上 V(n=1) 即可。 V(n=1) 即為 [[1], [1], [1], [1], [1]] （因為 n=1 時的組合有五個字母各一）。矩陣快速冪在 5x5 矩陣下的複雜度為 O(5^3 log(n))，忽略常數係數不看就是 O(log(n))。

到目前為止的做法在 LeetCode 上都算蠻普遍的做法，但除此之外我還發現了一個方法可以更進一步加速。

原先的矩陣快速冪方法複雜度是 O(⁵³ log(n))，我可以讓矩陣從 5x5 降為 4x4 達成複雜度 O(⁴³ log(n))。且目前在討論區沒有看到任何人提供類似的方法。

模式歸納

老實說我不知道這個方法該叫什麼名字好，有人知道的話請務必糾正我。

在原先的 5x5 矩陣中，我們在關心的是 a、e、i、o、u 五個字母的組合數；在我的方法裡面，我想從 a、e、i、o、u 的組合中更進一步尋找重覆的模式（我叫它 Pattern，後續將簡記作 P，第 k 個模式記作 Pk），以找到的模式作為基本組合單位去計算總組合數。

先呈上結論，從 n=1 開始一路遞增 n 往上找，很幸運的我找到了 4 個基本模式整個系統便趨於穩定、無新模式產出，而且最後一個模式──也就是 P4 ──是在 n=4，n=5 是第一次驗證沒有新模式產生──起初我以為範例中給了三個測資 n=1、n=2、n=5 只是巧合，但事情或許並非如此單純？

從題目規則中，每一個新的字母組合都是因為上一個字母存在的關係，例如出現 a 表示上一層可能有 e、i 或 u，如此說明每一個新模式的產生都跟上一層的模式有關，而我想找出這樣的關聯性（也就是題目規則約束）是如何作用在每一個模式上。

若每一層 n=k-1 都會經作一定規則的作用得到下一層 n=k 的組合，將 n=k 記作 Nk，則這個作用 F 可記作 F(Nk) 表示。

請跟著我一步步觀察字母組合的變化：

n=1 首先從五個字母開始，我將 aeiou 這個集合稱為 P1。我用空格與 n=2 切齊方便觀察上下關係。
n=2 得到一個 P1，剩餘的字母集合 aaeiu 我將它們記作 P2。到目前為止可以知道，P1 經過一個層次的作用到了下一層會生成一個 P1 和一個 P2，記作 F(P1) = P1 + P2。

N1 = a e  i    o  u = P1
N2 = e ai aeou iu a = aeiou aaeiu = P1 + P2F(P1) = F(N1) = N2
      = P1 + P2

驗證一下答案與測資是否相符。

Pk 長度代表的就是模式的組合數，所以 P1 為 5，P2 也為 5。

然後我們可以得到通式 Nk = F^(k-1)(N1) 。

N1 = P1 = 5
N2 = F(N1) = F(P1) = P1 + P2 = 5 + 5 = 10Nk = F(Nk-1) = F(F(Nk-2)) = ... = F^(k-2)(F(N2))
   = F^(k-1)(N1)

我們繼續往下一層推演：

N1 = P1
N2 = P1 P2N3 = ai e aeou e ai iu a aeou a e = aeiou aeiou aaeiu aaee
   = P1 + P1 + P2 + P3
   = 2*P1 + P2 + P3
   = 19F(P1) = P1 + P2F(P2) = F(N2 - P1)
      = F(N2) - F(P1)
      = N3 - (P1 + P2)
      = (2*P1 + P2 + P3) - (P1 + P2)
      = P1 + P3

將集合 aaee 標記為 P3 可得 F(P2) = P1 + P3 ，也就說明每一個 P2 經過 F 作用後會變成一個 P1 和一個 P3。

N1 = P1
N2 = P1 P2
N3 = 2*P1 + P2 + P3N4 = e aeou ai e ai iu a ai e aeou aeou a e e ai iu a e ai
   = aeiou aeiou aeiou aaeiu aaeiu aaee aaee ii
   = P1 + P1 + P1 + P2 + P2 + P3 + P3 + P4
   = 3*P1 + 2*P2 + 2*P3 + P4
   = 35F(P1) = P1 + P2
F(P2) = P1 + P3F(P3) = F(N3 - (2*P1 + P2))
      = F(N3) - 2*F(P1) - F(P2)
      = N4 - 2*(P1 + P2) - (P1 + P3)
      = (3*P1 + 2*P2 + 2*P3 + P4) - 2*(P1 + P2) - (P1 + P3)
      = P3 + P4

將集合 ii 標記為 P4 可得 F(P3) = P3 + P4 ，也就說明每一個 P3 經過 F 作用後會變成一個 P3 和一個 P4。

另外從上面的推論過程中可以發現，我們若想知道 F(Pk-1) 的值，需要從 Nk 的結果反推。目前推論到了 N4，因此需要繼續推敲 N5 以得到 F(P4)。

N1 = P1
N2 = P1 P2
N3 = 2*P1 + P2 + P3
N4 = 3*P1 + 2*P2 + 2*P3 + P4N5 = ... (DIY) ...
   = 7*P1 + 3*P2 + 4*P3 + P4
   = 68F(P1) = P1 + P2
F(P2) = P1 + P3
F(P3) = P3 + P4
F(P4) = F(N4 - (3*P1 + 2*P2 + 2*P3))
      = F(N4) - 3*F(P1) - 2*F(P2) - 2*F(P3)
      = N5 - 3*(P1 + P2) - 2*(P1 + P3) - 2*(P3 + P4)
      = (7*P1 + 3*P2 + 4*P3 + P4) - 3*(P1 + P2) - 2*(P1 + P3)
          - 2*(P3 + P4)
      = 2*P1 - P4

從 N5 我們可以看到沒有任何新模式產生，得到 F(P4) = 2*P1-P4 。

F(P4) 的這個結論有一個有趣的問題，前面的 F(Pk) 結論都只包含加法，我們可以理解為字串相聯，但-P4 如此的減法是合理的操作嗎？字串還有減法嗎？

若有注意到 P4 的字串集合為 ii ，則 F(P4) 可以得到 aeou aeou 這樣的集合，aeou 只比 P1 少了一個 i！

至於「字串還有減法嗎？」我覺得不必太糾結，因為字串真的沒有減法運算！這邊能夠寫作 -P4 都是因為 F(P3) 會產生一個 P4 給它抵消，因此我們可以把這裡理解為 F(P3) 產生的 P4 借給了 F(P4) 使用，F(P4) 可以說是負債了，因此以負號表示。

這樣的說法有一個前題，就是 F(P3) 須要和 F(P4) 在同一次 F 的作用中計算，所以我們只須驗證每一個包含了 P4 的 Nk 是不是一定都包含了 P3。

從 F(P2) 我們知道 P3 是從 P2 經過 F 而來，而 P2 是從 P1 經過 F 而來，最後每一個階段都一定有一個 P1，因為我們從 P1 出發，在每一層中 P1 都會產生自己！

小結論，從 N1 開始每一層都有 P1，從 N2 開始每一層都有 P2，從 N3 開始每一層都有 P3，只要在 N3 後運算 F(P4) 都一定會有 F(P3) 可以抵消 -P4。

至於 P4 的出現就沒這麼一致，因為前三者都是加法原理，只有它包含了減法的作用。

大結論，從 N=5 以後就沒有新模式出現，且所有組合都是 P1~P4 四種模式的組合。

實作歸納結果

從中間推導出的一個通式 Nk = F^(k-1)(N1) ，我們可以把作用 F 想作一個考量了四種模式的組合、大小為 4x4 的矩陣，就可以運用矩陣快速冪實現複雜度為 O(4³ log(N)) 的解決方案。

實作問題

我在以 JavaScript 實作的過程中遭遇到了瓶頸。

在我的測資中，按我取模數的程式碼位置不同，分別會在 n=31、n=144、n=333、n=871 都出現過問題，因此我特地將這些數字加入我的測資中。我觀察我計算出來的錯誤答案中常常出現負數！想也知道，組合數怎麼可能會是負的！

猜測有兩種情況：

1. 模數問題

假設 a, b 兩數每一輪疊代須進行 a — b 運算，運算後 a, b 會各自遞增再取模數，另外保證 a 遞增速度比 b 快且 a, b 的起始值 a ≥ b ≥ 0。虛擬碼如下：

MOD = 10**9 + 7
while (n--) {
    ans.push((a - b) % MOD)
    a = (a + 5) % MOD
    b = (b + 1) % MOD
}

不取模數的情況下，我們不必擔心結果 ans 中包含了負數，因為永遠 a ≥ b。在取模數的狀況中，a 可能剛好稍稍突破了 MOD，因此取完模數後反而比 b 還小了，下一次疊代算出的 a — b 就出現了負數。

這個狀況下要保證 a -b 永遠大於等於 0 還算好解，我們只需要將 a — b 改為 (a - b + MOD) % MOD 即可結果一致。

原理是基於模數的加法分配律：

(a - b + MOD) % MOD
    = ((a - b) % MOD + MOD % MOD) % MOD
    = (a - b) % MOD % MOD               // MOD % MOD === 0
    = (a — b) % MOD                     // x % MOD %MOD === x % MOD

2. 值域限制

也就是說，計算過程中有數值結果超越了 Number.MAX_SAFE_INTEGER 的限制。

簡單估算一下，Number.MAX_SAFE_INTEGER 為 16 位數，模數為 10 位數，假設有 a, b 兩數都取過模數，則 a + b 頂多逼近模數的兩倍，仍然是 10 位數的範圍內，但若 a * b 就非常有可能超越 16 位數。

換句話說，問題出自矩陣乘法中，每一個元素相乘（再加總）的部分。

疊代法

在這個實作中比較常出現負數狀況，且原因應該就是上述第一項模數問題，故在第 20 行處補上了修正方案。

然而在這個解法中，相比於五個變數的疊代，其實並沒有什麼決定性的突破，成績相當，約 70~80 ms。

矩陣快速冪

每一次疊代後的值都是前一次的值乘上常數係數後去作總和，說明我們可以將這個疊代寫作轉移矩陣，並以矩陣快速冪計算結果。

轉移矩陣的提取方式，我們可以先將每一個變數成分展開如下：

p1' = 1*p1 + 1*p2 + 0*p3 + 2*p4
p2' = 1*p1 + 0*p2 + 0*p3 + 0*p4
p3' = 0*p1 + 1*p2 + 1*p3 + 0*p4
p4' = 0*p1 + 0*p2 + 1*p3 + (-1)*p4

得到轉移矩陣 M1 以及轉置後的版本 M2（因為我代碼裡面用這個）：

| p1' |   | 1 1 0 2  |   | p1 |
| p2' |   | 1 0 0 0  |   | p2 |
| p3' | = | 0 1 1 0  | * | p3 |               // M1
| p4' |   | 0 0 1 -1 |   | p4 |                            | 1 1 0 0 |
                            | 1 0 1 0 |
        = | p1 p2 p3 p4 | * | 0 0 1 1 |       // M2
                            | 2 0 0 -1|

像我們從疊代這個邏輯推過來，就好比在 M1 中橫著一列一列讀：第一列為 | 1 1 0 2 | 說明 p1' 由 1 個 p1 、1 個 p2、0 個 p3、2 個 p4 構成。

至於 M1 豎著讀會是什麼意思呢？

如果有回想起我們上面模式歸納的結論的話，我們有以下關係：

F(P1) = P1' + P2'
F(P2) = P1' + P3'
F(P3) = P3' + P4'
F(P4) = 2*P1' - P4'

這邊我故意將 ' 標上去，因為 F(P1) 說明的是當前的 P1 會貢獻一個下一輪的 P1 和 P2。

我們可以將 M1 矩陣兩邊的向量交換如下，須注意矩陣乘法的順序和轉置。

| p1 |                         | 1 1 0 2  |
| p2 |                         | 1 0 0 0  |
| p3 | = | p1' p2' p3' p4' | * | 0 1 1 0  |
| p4 |                         | 0 0 1 -1 |

這樣就能看出和模式歸納的結論的關係了，其實不論 M1 或 M2 差別在於下一輪的變數和這一輪變數在等式中的哪一方而已。解讀方式稍微不一樣，在套用通式時初始向量的在乘號兩邊的位置和維度都稍有不同。

在以 JavaScript 實作矩陣快速冪的時候讓我折騰了很久，主因就是上述問題中的第二項值域問題。

我目前唯一的解決方案就是 BigInt。

於是乎有了以下程式碼，我將所有矩陣數值和會和矩陣一起運算的數值都換成了 BigInt。

以為只要努力就能得到收穫嗎？這個世界的規則可不是這樣玩的。

在這個算法中，大概取得了 120~130 ms 的成績，大概慢了模式歸納疊代法的 33% （只有其 67% 效率）。根本原因大概就是 BigInt 的效率問題了。

重新思考問題，當初我會使用 BigInt 就是因為值域問題，但不是每次乘法都會超出值域。

有了這想法之後，於是我有了修正版本如下。

在第 12、13 行的部分我加上了判斷式，只要相乘突破值域限制的值，我就改以 BigInt 相乘並取模數，因為取過模數數值就降回了值域內，因此我又將它轉回了 Number。

聽到這邊應該有感受到，其實還有優化空間了吧……但折騰得我心好累。

在這個實現中，再次取得了 70~80 ms 的成績，與不論哪一種疊代法並列。

Python3 登場

既然 JavaScript 在值域問題上碰了一頭灰，我突然想起另一個好夥伴 Python3 的整數似乎沒有域值上限……哪尼口雷！？

於是乎，我想知道它是不是跟 BigInt 一樣會讓我失望，而有了以下的 Python 程式碼。

出乎意料的一鳴驚人，從 3.6 萬個 AC 和 6 萬多次提交中贏了 100% 的 Python3 提交！可喜可賀！

從這次的練習中，我想對於自己最大的突破就是找到了一套方法是討論區沒看到的，由於事先透過理論證實可行，於是我才會不斷想突破語言的限制，驗證最終的方法正確且效率良好。

這次最大的不足莫過於對模數運算的陌生，以及對大數處理缺乏知識，也在這次的嘗試中不斷的補充知識點以克服難關。

這次還有一個收穫便是複習了矩陣的運算，以及如何實作矩陣快速冪、提取轉移矩陣……等等知識。

希望還會有下次機會記錄自己的努力和突破。

如果有人願意看到最後，我抱著由衷感謝和佩服的心。

感謝閱讀！

備註

英文精簡版說明發表於 LeetCode 討論區

https://leetcode.com/problems/count-vowels-permutation/discuss/1322330/Python3-4x4-matrix-exponentiation-beat-100-of-Python3-submissions

LeetCode 解題紀錄 #1

1220. Count Vowels Permutation

└─解題難度：HARD

Count Vowels Permutation — LeetCode

Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared…

題目說明

實戰成績

JavaScript

Python3

解題分析

動態規劃

疊代 + 簡化資結

矩陣快速冪

模式歸納

實作歸納結果

實作問題

疊代法

矩陣快速冪

Python3 登場

備註

Written by Kevin Cheng