推 JIWP: 大師 11/14 14:29
推 Ceelo: 靠北 離散數學考這題 11/14 14:35
→ ZooseWu: 我已經忘記離散數學在教什麼了 11/14 15:04
1930. Unique Length-3 Palindromic Subsequences
給你一個字串
字串的子序列可以組成一個三個字元的回文字串
回傳子字串所有可能的數量
* 子序列 = 移除某些元素但是不改變順序
Input: s = "aabca" Output: 3
- "aba" ("aabca")
- "aaa" ("aabca")
- "aca" ("aabca")
Input: s = "adc" Output: 0
Input: s = "bbcbaba" Output: 4
- "bbb" ("bbcbaba")
- "bcb" ("bbcbaba")
- "bab" ("bbcbaba")
- "aba" ("bbcbaba")
Intuition:
這題我想了三個解法
1. 用兩個陣列分別記錄字母頭尾出現的位置
最後算他們中間出現多少字母
2. 用一個二維陣列紀錄有沒有出現過
如果有就結果+1
3. 用一個二維陣列紀錄回文的狀態
如果出現前半就0->1
如果出現後半就1->2
前兩個方法都有缺陷
最後是用第三個方法解出來的
Approach:
首先宣告一個二維陣列紀錄回文的狀態
以及一個Set紀錄前面出現過的字母
如果現在跑到"b"
然後前面已經出現過"a"
那就把[0][1]的狀態0->1
後面如果在次出現a
就把狀態1->2並把結果+1
所以我們跑迴圈的時候
先檢查前面有沒有出現過[檢查的字元][所有前面出現過的字元]
如果有就把狀態1->2
接下來把[所有前面出現過的字元][檢查的字元]的狀態0->1
最後把字元加到已經出現過的陣列中
這一題的時間複雜度是O(n*26)
好像一樣算O(n)
然後空間複雜度是O(26*26)
所以是O(1)
TS code:
const GetCharIndex = (s: string): number => {
return s.charCodeAt(0) - "a".charCodeAt(0)
}
function countPalindromicSubsequence (s: string): number {
const diffChar: number[][] = Array.from(Array(26), () =>
(Array(26).fill(0)))
const frontCharIndexes = new Set<number>()
let answer = 0
for (let i = 0; i < s.length; i++) {
const index = GetCharIndex(s[i])
for (const frontCharIndex of frontCharIndexes) {
if (diffChar[index][frontCharIndex] === 1) {
diffChar[index][frontCharIndex] = 2
answer++
}
}
for (const frontCharIndex of frontCharIndexes) {
if (diffChar[frontCharIndex][index] === 0) {
diffChar[frontCharIndex][index] = 1
}
}
frontCharIndexes.add(index)
}
return answer
}
--
Zoosewu
Yoututbe顯示PTT推文
可以在各個網站追實況或Live時使用
預覽圖: https://i.imgur.com/ZhtXdAJ.png https://i.imgur.com/WqbLNV3.png
完整介紹: https://github.com/zoosewu/PTTChatOnYoutube/tree/master/homepage
支援的網站: Youtube Twitch Holotools Niji-mado Holodex
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.32.229.33 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1699943347.A.21D.html