336. Palindrome Pairs
題目網址：https://leetcode.cn/problems/palindrome-pairs/
題意：給一單字互不相同的 string list words, 找出所有不同的 index pair (i, j), 使得 word[i] + word[j] 為迴文。
Solution 1：（TLE 無法通過）
想法：利用 Trie
首先, 我們把所有 words[i] 給 insert 到 trie 中
若 string words[i] 存在迴文 pair, 則可以先將 words[i] 拆成 s1 和 s2, 也就是說 words[i] = s1 + s2
若 s1 的部分為迴文, 假設 words[i] = XXXXabc, 其中 s1 = XXXX 表示為迴文, s2 = abc。若存在迴文, 則應存在 left = reverse(s2) = cba, 使得 left + words[i] = cbaXXXXabc 為迴文, 得到迴文 pair 為 {leftIdx, i}
若 s2 的部分為迴文, 假設 words[i] = abcXX ...
642. Design Search Autocomplete System
題目網址：https://leetcode.cn/problems/design-search-autocomplete-system/
題意：為搜尋引擎設計一個自動補全系統, 用戶會輸入一個句子(最少包含一個 char, 並以 '#' 結尾)。
給一 string list sentence 和一整數 times, 長度皆為 n, 其中 sentence[i] 為之前輸入的句子, 而 times[i] 為該句子輸入的相應次數。對於 '#' 以外的每個輸入 char, 返回前 3 個熱門句子, 這些句子的 prefix 和已經輸入的句子的部分相同。
以下是詳細規則：
一個句子的熱度定義為歷史上用戶輸入該句子的總次數。
返回前 3 個熱門句子需依照熱度由高到低排序。若有多條熱度相同的句子, 則按照 ASCII 碼的順序輸出(ASCII 碼越小越前面)。
如果滿足條件的句子個數 < 3, 則將它們全部輸出。
如果輸入特殊 char '#', 則代表句子結束了, 請返回 empty list []。
實現 AutocompleteS ...
425. Word Squares
題目網址：https://leetcode.cn/problems/word-squares/
題意：給一不重複的 string set words, 返回其中所有的 word square。words 中的同一個單字可以被多次使用, 以任意順序返回答案。
word square 的定義：從第 k 列和第 k 行來看都是相同的 string, 其中 0 ≤ k ≤ max(numRows, numColumns)。
e.g. words = ["ball","area","lead","lady"] 為 word square, 因為每個單字從水平和垂直方向上來看都是相同的。
Solution：
想法：利用 Trie + DFS + Backtracking, 逐列填入單字, 新的一列填入的單字可由前面的單字得到, 其中第 idx 列的單字之 prefix 可由前面每個單字的第 idx + 1 個字母所串連
e.g. words = ["wall","able" ...
1203. Sort Items by Groups Respecting Dependencies
題目網址：https://leetcode.cn/problems/sort-items-by-groups-respecting-dependencies/
題意：有 n 個 item, 其中每個 item 可以不屬於任何 group, 或者屬於 m 個 group 中的其中一個。group[i] 代表第 i 個 item 所屬的 group, 如果第 i 個 item 不屬於任何 group, 則 group[i] = -1。item 和 group 都從 0 開始編號的。可能存在 group 不負責任何 item。
返回 sorted list 滿足:
同一 group 的 item 排序後應彼此相鄰
item 之間存在一定的依賴關係 beforeItems, 其中 beforeItems[i] 代表進行第 i 個 item 前應完成的所有 item
如果存在多個解, 返回其中一個即可。若沒有解, 則返回 empty list。
注意：beforeItems[i] 沒有重複的元素。
Solution：
想法：利用 Topological Sort + BFS, 首先我們 ...
278. First Bad Version
題目網址：https://leetcode.cn/problems/first-bad-version/
題意：假設你有 n 個版本 [1, 2, ..., n], 請找出導致之後所有版本出錯的第一個錯誤的版本。
你可以通過調用 bool isBadVersion(version) API 來判斷 version 是否出錯。
盡量減少調用 API 的次數。
Solution：
想法：利用 Binary Search
class Solution {public: int firstBadVersion(int n) { int left = 0, right = n - 1; while (left <= right) { const int mid = left + (right - left) / 2; if (isBadVersion(mid)) { right = mid - 1; } ...