269. Alien Dictionary
題目網址：https://leetcode.cn/problems/alien-dictionary/
題意：有一種使用英文的外星語言, 其字母的順序與英文的順序不同。
給一 word list words 作為該外星語言的字典, wrods 中的 string 已按照外星語言的字母順序進行排序。
請按照 words 還原出該語言中已知的字母順序, 並按字母的遞增順序排列。若不存在合法的字母順序, 則返回 ""。若存在多種合法的順序, 則返回任意一種即可。
string s 小於 string t 有兩種情況:
在第一個不同的字母處, s 的字母順序在 t 的字母之前
如果前 min(s.length, t.length) 個字母都相同, 且 s.length < t.length
words[i] 僅由小寫字母組成。
Solution：
想法：利用 Topological Sort + BFS, 類似 207. Course Schedule, 相鄰兩個 word 可建構一條順序
e.g. words = ["wrt",&quo ...
329. Longest Increasing Path in a Matrix
題目網址：https://leetcode.cn/problems/longest-increasing-path-in-a-matrix/
題意：給一 m x n 整數矩陣 matrix, 找出其中最長遞增路徑的長度。
對於每個 cell, 可以往上、下、左、右四個方向移動。
不能在對角線方向上移動 or 移動到邊界外。
Solution：
想法：利用 DFS + DP, 其中 dp[i][j] 紀錄以 (i, j) 為起點的最長遞增路徑之長度。透過 DP 可避免重複計算。e.g. 假設先計算完 dfs(A), 只後執行 dfs(C) 時, 發現 C 會拜訪 A, 透過 DP 可直接得到先前計算過的 dfs(A), 而不用重新計算
class Solution {public: int longestIncreasingPath(vector<vector<int>>& matrix) { m = matrix.size(), n = matrix[0].size(); dp.resize ...
115. Distinct Subsequences
題目網址：https://leetcode.cn/problems/distinct-subsequences/
題意：給兩 string s 和 t, 返回在 s 的 subsequence 中 t 出現的個數。
題目保證答案符合 32-bit 有號整數的範圍。
Solution 1：
想法：利用 DP
1. 定義狀態：
dp[i][j]：s[1:i]中 subseq 為 t[1:j] 的個數
2. 得到轉移方程：
當 s[i] == t[j] 時, 有兩種情況：
用 s[i] 去匹配 t[j]： ➔ 則問題變成 s[1:(i-1)] 中 subseq 為 t[1:(j-1)] 的數量 ➔ dp[i][j] = dp[i - 1][j - 1]
不用 s[i] 去匹配 t[j]： ➔ 則問題變成 s[1:(i-1)] 中 subseq 為 t[1:j] 的數量 ➔ dp[i][j] = dp[i - 1][j]
否則, 問題變成 s[1:(i-1)] 中 subseq 為 t[1:j] 的數量➔ dp[i][j] = dp[i - 1][j]
3. ...
72. Edit Distance
題目網址：https://leetcode.cn/problems/edit-distance/
題意：給兩 string word1 和 word2, 返回將 word1 轉換成 word2 的最少操作數。
可對單字進行以下操作：
插入一個 char
刪除一個 char
替換一個 char
!https://i.imgur.com/Lw9oEAc.png
Solution：
想法：利用 DP
1. 定義狀態：
dp[i][j]：word1[1:i] 轉換成 word2[1:j] 的最少操作數
2. 得到轉移方程：
若 word1[i] == word2[j], 則問題變成 word1[1:(i-1)] 轉換成 word2[1:(j-1)] 的最少操作數➔ dp[i][j] = dp[i - 1][j - 1]
否則, 有三種情況：
word1[1:i] 插入 word2[j], 則問題變成 word1[1:i] 轉換成 word2[1:(j-1)] 的最少操作數 + 1（+1 是因為插入操作） ➔ dp[i][j] = dp[i][j - 1] + 1
word ...
10. Regular Expression Matching
題目網址：https://leetcode.cn/problems/regular-expression-matching/
題意：給你一個 string s 和一個 string pattern p，請實現一個支持 '.' 和 '*' 的正則表達式匹配。
'.' 匹配任意單個 char
'*' 匹配 0 個 or 多個前面的那一個元素
所謂匹配, 是要涵蓋整個 s 的, 而不是部分 string。
Solution：
想法：利用 DP, 其中 dp[i][j] 判斷 s[0 ~ (i - 1)] 和 p[0 ~ (j - 1)] 是否匹配，每次判斷當前 s、p 的最後一個 char 是否匹配
若 s[i - 1] == p[j - 1] 或 p[j - 1] == '.' : 代表當前 s、p 的最後一個 char 匹配, 則當前 s、p 是否匹配取決於前面的 substring, 也就是說 dp[i][j] = dp[i - 1][j - 1]
若 p[j - 1] == '* ...